作者:
sixB (6B)
2025-02-25 23:25:371524.
今天這題我覺得蠻好玩的:3
subarray ㄧ格一格dp加起來
原本以為是要求subset
還在想哪邊要加mod 超麻煩==
在那邊算數學
class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
int mod = 1e9 + 7;
int even = 0, odd = 0, res = 0;
for(int& i: arr){
if(i%2 == 1){ // i odd
swap(odd, even);
odd++;
}
else even++;
// mod
res += odd;
res %= mod;
}
return res;
}
int numOfSubsets(vector<int>& arr) {
int even = 0, odd = 0;
for(int& i: arr){
if(i%2) odd++;
else even++;
}
// count all subset odd
int oddset = pow(2, odd-1); //odd number
int evenset = pow(2, even); //all
int res = oddset * evenset;
return res;
}
};
取奇數或偶數個都是2^n-1欸
還跑去找證明
好崇拜這些數學好的人
我也想把數學學好