#include <bits/stdc++.h> #define ll long long int using namespace std; const int maxn=3*1e5+5; const ll mod=1e9+7; ll a[maxn], dp[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; ll suma=0; for(int i=1; i<=n; ++i) { cin>>a[i]; suma+=a[i]; } if(suma<mod) { suma=0; for(int i=1; i<=n; ++i) { a[i]%=2; if(a[i]==1) ++suma; } if(suma%2==1) { cout<<"0"; return 0; } bool otw=0; //int pot=0; ll wyn=1; for(int i=1; i<n; ++i) { if(a[i]==1) { if(!otw) otw=1; else { //++pot; otw=0; wyn<<=1; wyn%=mod; } } else if(!otw) { //++pot; wyn<<=1; wyn%=mod; } } //cout<<pot<<"\n"; cout<<wyn; } else { dp[0]=1; if((a[1]%mod)%2==0) dp[1]=1; else dp[1]=0; for(int i=2; i<=n; ++i) { dp[i]=0; ll sum=0; for(int j=i; j>=1; --j) { sum+=a[j]; sum%=mod; if(sum%2==0) { dp[i]+=dp[j-1]; dp[i]%=mod; } } } cout<<dp[n]; } 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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | #include <bits/stdc++.h> #define ll long long int using namespace std; const int maxn=3*1e5+5; const ll mod=1e9+7; ll a[maxn], dp[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; ll suma=0; for(int i=1; i<=n; ++i) { cin>>a[i]; suma+=a[i]; } if(suma<mod) { suma=0; for(int i=1; i<=n; ++i) { a[i]%=2; if(a[i]==1) ++suma; } if(suma%2==1) { cout<<"0"; return 0; } bool otw=0; //int pot=0; ll wyn=1; for(int i=1; i<n; ++i) { if(a[i]==1) { if(!otw) otw=1; else { //++pot; otw=0; wyn<<=1; wyn%=mod; } } else if(!otw) { //++pot; wyn<<=1; wyn%=mod; } } //cout<<pot<<"\n"; cout<<wyn; } else { dp[0]=1; if((a[1]%mod)%2==0) dp[1]=1; else dp[1]=0; for(int i=2; i<=n; ++i) { dp[i]=0; ll sum=0; for(int j=i; j>=1; --j) { sum+=a[j]; sum%=mod; if(sum%2==0) { dp[i]+=dp[j-1]; dp[i]%=mod; } } } cout<<dp[n]; } return 0; } |