#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; if(n<3000){ int a[n]; for(int i = 0; i< n; i++){ cin >> a[i]; } int b[n+1]; b[0]=0; for(int i = 0; i< n; i++){ b[i+1]=b[i]+a[i]; b[i+1]%=1000000007; } long long c[n+1]; c[0]=1; for(int i = 1; i< n+1; i++) c[i]=0; for(int i = 0; i<= n; i++){ for(int j = i-1; j>=0; j--){ if(((b[i]-b[j]+1000000007)%1000000007)%2==0){ // cout << i << ' ' << j << '\n'; c[i]+=c[j]; c[i]%=1000000007; } } // cout << c[i] << "\n\n"; } cout << c[n]; }else{ int a[n]; for(int i = 0; i< n; i++){ cin >> a[i]; } int b[n+1]; b[0]=0; int v2=1, v1=0; for(int i = 0; i< n; i++){ b[i+1]=b[i]+a[i]; } for(int i = 0; i< n; i++){ if(b[i+1]%2==1){ if(b[i]%2==1){ v1+=v1; v1%=1000000007; }else{ v1+=v2; v1%=1000000007; } }else{ if(b[i]%2==1){ v2+=v1; v2%=1000000007; }else{ v2+=v2; v2%=1000000007; } } } if(b[n]%2){ cout << v1; }else{ cout << v2; } } 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; if(n<3000){ int a[n]; for(int i = 0; i< n; i++){ cin >> a[i]; } int b[n+1]; b[0]=0; for(int i = 0; i< n; i++){ b[i+1]=b[i]+a[i]; b[i+1]%=1000000007; } long long c[n+1]; c[0]=1; for(int i = 1; i< n+1; i++) c[i]=0; for(int i = 0; i<= n; i++){ for(int j = i-1; j>=0; j--){ if(((b[i]-b[j]+1000000007)%1000000007)%2==0){ // cout << i << ' ' << j << '\n'; c[i]+=c[j]; c[i]%=1000000007; } } // cout << c[i] << "\n\n"; } cout << c[n]; }else{ int a[n]; for(int i = 0; i< n; i++){ cin >> a[i]; } int b[n+1]; b[0]=0; int v2=1, v1=0; for(int i = 0; i< n; i++){ b[i+1]=b[i]+a[i]; } for(int i = 0; i< n; i++){ if(b[i+1]%2==1){ if(b[i]%2==1){ v1+=v1; v1%=1000000007; }else{ v1+=v2; v1%=1000000007; } }else{ if(b[i]%2==1){ v2+=v1; v2%=1000000007; }else{ v2+=v2; v2%=1000000007; } } } if(b[n]%2){ cout << v1; }else{ cout << v2; } } return 0; } |