本番間に合わず。
https://yukicoder.me/problems/no/1222
問題
- 1,0,1のいずれかの値を取るN要素の数列Aを考える。
以下の条件がいくつか与えられる。
- 区間A[L]~A[R]の積が指定された値である
条件を満たすAの組み合わせは何通りか。
なお、各条件でRは異なる。
解法
まず条件のうち1か-1かは後で考えるとして、積は0か0でないかを考えよう。
以下を考える。
f(n,k) := Aの先頭n要素まで決めたとき、最後のkの位置が0であるような組み合わせ
f(0,0)からf(n,*)を順に求めて行こう。
区間加算・区間乗算・区間和を求められるSegTreeを使いfを更新していく。
今からnを処理するとき、
- R=nである条件がない
- n要素は0,1,-1のどれが入ってもよい。そこで1,-1を入れるケースとしてf(n,k)=2*f(n-1,k)、0を入れるケースとしてf(n,n)=sum(f(n-1,*))を取る。
- R=nである条件があり、積は0である
- L~Rの間に0が1個以上なければならない。よって f(n,k)はk<Lでは0、L≦k<Rでは2*f(n-1,k)、f(n,n)=sum(f(n-1,*))
- R=nである条件があり、積は0でない
- L~Rの間に0があってはならない。よって f(n,k)=2*f(n-1,k)、f(n,n)=0
最後sum(f(N,*))を取れば、積が0である条件を満たす組み合わせが得られる。
あとは積が1,-1の条件だが、これはそのような条件がm個ある場合、全体を2^mで割ればよい。
結局正負の数のパリティを合わせる作業なので、条件毎に1要素は自由に選べないことになるためである。
int N,M; int L[202020],R[202020],P[202020]; int cand[202020]; const ll mo=1000000007; template<class V,int NV> class SegTree_MulAdd { public: vector<V> sum,mul,add; // sum stores val after muladd SegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return sum[k]; x=max(x,l); y=min(y,r); V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1); return (ret*mul[k]+add[k]*(y-x))%mo; } void propagate(int k,int s) { (mul[k*2]*=mul[k])%=mo; (add[k*2]*=mul[k])%=mo; (sum[k*2]*=mul[k])%=mo; (add[k*2]+=add[k])%=mo; (sum[k*2]+=add[k]*s%mo*(mo+1)/2)%=mo; (mul[k*2+1]*=mul[k])%=mo; (add[k*2+1]*=mul[k])%=mo; (sum[k*2+1]*=mul[k])%=mo; (add[k*2+1]+=add[k])%=mo; (sum[k*2+1]+=add[k]*s%mo*(mo+1)/2)%=mo; mul[k]=1; add[k]=0; } void domul(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { (mul[k]*=v)%=mo; (add[k]*=v)%=mo; (sum[k]*=v)%=mo; } else if(l < y && x < r) { propagate(k,r-l); domul(x,y,v,l,(l+r)/2,k*2); domul(x,y,v,(l+r)/2,r,k*2+1); sum[k]=(sum[k*2]+sum[k*2+1])%mo; } } void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { (add[k]+=v)%=mo; (sum[k]+=(r-l)*v)%=mo; } else if(l < y && x < r) { propagate(k,r-l); doadd(x,y,v/mul[k],l,(l+r)/2,k*2); doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1); sum[k]=(sum[k*2]+sum[k*2+1])%mo; } } }; SegTree_MulAdd<ll,1<<18> st; void solve() { int i,j,k,l,r,x,y; string s; MINUS(cand); cin>>N>>M; ll rev=(mo+1)/2; ll p=1; FOR(i,M) { cin>>L[i]>>R[i]>>P[i]; cand[R[i]]=i; if(P[i]) p=p*rev%mo; } st.doadd(0,1,p); for(i=1;i<=N;i++) { if(cand[i]==-1) { ll v=st.getval(0,i); st.domul(0,i,2); st.doadd(i,i+1,v); } else if(P[cand[i]]==0) { ll v=st.getval(0,i); st.domul(0,i,2); st.doadd(i,i+1,v); st.domul(0,L[cand[i]],0); } else { st.domul(0,L[cand[i]],2); st.domul(L[cand[i]],i,0); } } ll v=st.getval(0,N+1); cout<<v%mo<<endl; }
まとめ
SegTree使ったけど、BITでもいい気がしてきた。