#include<iostream> #include<vector> using namespace std; const int MOD = 1000000007; vector<long long> P; int check(int i,int j) { //cout<<"P[j+1] "<<P[j+1]<<" P[i] "<<P[i]<<endl; if(((P[j+1]-P[i])%MOD)%2==0) return 1; return 0; } int main() { ios_base::sync_with_stdio(0); int n; cin>>n; vector<int> T(n); P.resize(n+1); for(auto &i : T) cin>>i; P[1]=T[0]; for(int i=1 ; i<n ; i++) {P[i+1]=P[i]+T[i];} vector<long long> DP(n,0); for(int i=0 ; i<n ; i++) { for(int j=0 ; j<i ;j++) { //cout<<"j "<<j<<" i "<<i<<endl; //cout<<check(j,i)<<endl; DP[i]+=(DP[j]*check(j+1,i))%MOD; } if((P[i+1]%MOD)%2==0) DP[i]++; DP[i]%=MOD; //cout<<"I:"<<i<<" DP:"<<DP[i]<<endl; } cout<<DP[n-1]<<endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include<iostream> #include<vector> using namespace std; const int MOD = 1000000007; vector<long long> P; int check(int i,int j) { //cout<<"P[j+1] "<<P[j+1]<<" P[i] "<<P[i]<<endl; if(((P[j+1]-P[i])%MOD)%2==0) return 1; return 0; } int main() { ios_base::sync_with_stdio(0); int n; cin>>n; vector<int> T(n); P.resize(n+1); for(auto &i : T) cin>>i; P[1]=T[0]; for(int i=1 ; i<n ; i++) {P[i+1]=P[i]+T[i];} vector<long long> DP(n,0); for(int i=0 ; i<n ; i++) { for(int j=0 ; j<i ;j++) { //cout<<"j "<<j<<" i "<<i<<endl; //cout<<check(j,i)<<endl; DP[i]+=(DP[j]*check(j+1,i))%MOD; } if((P[i+1]%MOD)%2==0) DP[i]++; DP[i]%=MOD; //cout<<"I:"<<i<<" DP:"<<DP[i]<<endl; } cout<<DP[n-1]<<endl; return 0; } |