#include <bits/stdc++.h> using namespace std; long long e=1000*1000*1000+7; long long pref[300*1000+6]; long long f[300*1000+5]; long long sym_v2(int n){ //cout << "czek"<<endl; bool parz=1; long long wynik=-1; for (int i=0; i<n;i++){ if ((pref[i+1]-pref[i])%2){ parz=!parz; if (parz){ wynik*=2; if (wynik==-2){ wynik=1; } wynik%=e; } } else if (parz){ wynik*=2; if (wynik==-2){ wynik=1; } } //cout << (pref[i+1]-pref[i])%2<<" "<<parz<<" "<<wynik<<" "<<endl; } //cout << parz<<endl; if (!parz){ return 0; }else{ return wynik; } } long long czyprzedzial_mop( int j, int i){ long long tmp = pref[i+1] - pref[j]; if (tmp<0){ tmp+=e; } return (tmp%e); } int main(){ int n; cin >> n; pref[0]=0; bool czek = 1; for (int i=0;i<n;i++){ long long l=0; cin >> l; pref[i+1]=(pref[i]+l)%e; f[i]=0; if (l>100){ czek=0; } } if (czek){ cout << sym_v2(n)%e<<endl; }else{ for (int i=0;i<n;i++){ for (int j=0;j<i;j++){ f[i]+=f[j]*(long long)(czyprzedzial_mop(j+1,i)%2==0); f[i]%=e; //cout <<f[j]<<" "<<j+1<<" "<<i<<" "<<czyprzedzial_mop(pref,j+1,i)<<";"<<endl; } f[i]+=(long long)(czyprzedzial_mop(0,i)%2==0); f[i]%=e; //cout << i<<" "<<f[i]<<endl; } cout<<f[n-1]%e<<endl; } }
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 70 71 72 73 74 75 76 77 78 79 80 | #include <bits/stdc++.h> using namespace std; long long e=1000*1000*1000+7; long long pref[300*1000+6]; long long f[300*1000+5]; long long sym_v2(int n){ //cout << "czek"<<endl; bool parz=1; long long wynik=-1; for (int i=0; i<n;i++){ if ((pref[i+1]-pref[i])%2){ parz=!parz; if (parz){ wynik*=2; if (wynik==-2){ wynik=1; } wynik%=e; } } else if (parz){ wynik*=2; if (wynik==-2){ wynik=1; } } //cout << (pref[i+1]-pref[i])%2<<" "<<parz<<" "<<wynik<<" "<<endl; } //cout << parz<<endl; if (!parz){ return 0; }else{ return wynik; } } long long czyprzedzial_mop( int j, int i){ long long tmp = pref[i+1] - pref[j]; if (tmp<0){ tmp+=e; } return (tmp%e); } int main(){ int n; cin >> n; pref[0]=0; bool czek = 1; for (int i=0;i<n;i++){ long long l=0; cin >> l; pref[i+1]=(pref[i]+l)%e; f[i]=0; if (l>100){ czek=0; } } if (czek){ cout << sym_v2(n)%e<<endl; }else{ for (int i=0;i<n;i++){ for (int j=0;j<i;j++){ f[i]+=f[j]*(long long)(czyprzedzial_mop(j+1,i)%2==0); f[i]%=e; //cout <<f[j]<<" "<<j+1<<" "<<i<<" "<<czyprzedzial_mop(pref,j+1,i)<<";"<<endl; } f[i]+=(long long)(czyprzedzial_mop(0,i)%2==0); f[i]%=e; //cout << i<<" "<<f[i]<<endl; } cout<<f[n-1]%e<<endl; } } |