#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct ciag { int pocz; int kon; int war; vector<int> v; }; ciag t[1000005]; string s; int n, il=0, a, mini=1000005, maks, pos=1, dop[1000005], mod=1000000007; bool b[2][1000005]; bool cmp(ciag x, ciag y) { if(x.pocz>y.pocz) return 0; else if(x.pocz==y.pocz) { if(x.kon>y.kon) return 0; else return 1; } else return 1; } int pot(int x) { if(x==0) return 1; if(x%2==1) return (2*pot(x-1))%mod; long long w=pot(x/2); return (w*w)%mod; } int main() { scanf("%d", &n); cin.ignore(); getline(cin,s); for(int i=0;i<s.size();i++) { if(s[i]=='(') { t[il].pocz=mini; t[il].kon=maks; mini=1000005; maks=0; il+=1; } else if(s[i]=='~') { i+=2; a=0; while(s[i]-'0'<10 && s[i]-'0'>=0) { a*=10; a+=s[i]-'0'; i+=1; } a=-a; t[il].v.push_back(a); mini=min(mini,-a); maks=max(maks,-a); } else if(s[i]-'0'<10 && s[i]-'0'>=0) { a=0; while(s[i]-'0'<10 && s[i]-'0'>=0) { a*=10; a+=s[i]-'0'; i+=1; } t[il].v.push_back(a); mini=min(mini,a); maks=max(maks,a); } } t[il].pocz=mini; t[il].kon=maks; t[il+1].kon=1000005; t[il+1].pocz=1000005; sort(t+1,t+il+1,cmp); for(int i=1;i<=il+1;i++) { for(int j=pos;j<t[i].pocz;j++) dop[j]=i; pos=t[i].pocz; } for(int i=il;i>0;i--) { for(int j=0;j<t[i].v.size();j++) if(t[i].v[j]<0) b[0][-t[i].v[j]]=1; else b[1][t[i].v[j]]=1; for(int j=t[i].kon;j>=t[i].pocz;j--) if(j<=t[i+1].kon) { if(dop[j]==il+1) t[i].war+=pot(n-j); else t[i].war+=t[dop[j]].war; if(b[0][j] && b[1][j]) t[i].war-=1; t[i].war=t[i].war%mod; } } printf("%d", t[1].war); 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 95 96 97 98 99 100 101 102 103 104 | #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct ciag { int pocz; int kon; int war; vector<int> v; }; ciag t[1000005]; string s; int n, il=0, a, mini=1000005, maks, pos=1, dop[1000005], mod=1000000007; bool b[2][1000005]; bool cmp(ciag x, ciag y) { if(x.pocz>y.pocz) return 0; else if(x.pocz==y.pocz) { if(x.kon>y.kon) return 0; else return 1; } else return 1; } int pot(int x) { if(x==0) return 1; if(x%2==1) return (2*pot(x-1))%mod; long long w=pot(x/2); return (w*w)%mod; } int main() { scanf("%d", &n); cin.ignore(); getline(cin,s); for(int i=0;i<s.size();i++) { if(s[i]=='(') { t[il].pocz=mini; t[il].kon=maks; mini=1000005; maks=0; il+=1; } else if(s[i]=='~') { i+=2; a=0; while(s[i]-'0'<10 && s[i]-'0'>=0) { a*=10; a+=s[i]-'0'; i+=1; } a=-a; t[il].v.push_back(a); mini=min(mini,-a); maks=max(maks,-a); } else if(s[i]-'0'<10 && s[i]-'0'>=0) { a=0; while(s[i]-'0'<10 && s[i]-'0'>=0) { a*=10; a+=s[i]-'0'; i+=1; } t[il].v.push_back(a); mini=min(mini,a); maks=max(maks,a); } } t[il].pocz=mini; t[il].kon=maks; t[il+1].kon=1000005; t[il+1].pocz=1000005; sort(t+1,t+il+1,cmp); for(int i=1;i<=il+1;i++) { for(int j=pos;j<t[i].pocz;j++) dop[j]=i; pos=t[i].pocz; } for(int i=il;i>0;i--) { for(int j=0;j<t[i].v.size();j++) if(t[i].v[j]<0) b[0][-t[i].v[j]]=1; else b[1][t[i].v[j]]=1; for(int j=t[i].kon;j>=t[i].pocz;j--) if(j<=t[i+1].kon) { if(dop[j]==il+1) t[i].war+=pot(n-j); else t[i].war+=t[dop[j]].war; if(b[0][j] && b[1][j]) t[i].war-=1; t[i].war=t[i].war%mod; } } printf("%d", t[1].war); return 0; } |