ライブラリ化しておこうかなぁ。
http://codeforces.com/contest/551/problem/D
問題
N要素の数列A[i]を考える。
各要素は2^L以下でなければならない。
(A[0] and A[1]) or (A[1] and A[2]) or ... or(A[N-2] and A[N-1]) == K
となるA[i]は何通りあるか。
解法
二進数表記の各桁毎に両辺をそろえることを考える。
A[i]を0か1の2値として上式左辺の結果が0または1になるケースを考える。
0になるケースを求める方が簡単。
- A[i-1] and A[i]は0でなければならないので:
- A[i-1]の値を問わずA[i]は0を取れる
- A[i]が1となれるのは、A[i-1]が0時だけ
この条件から、A[0]~A[N-1]に対し上式が0となる組み合わせを求められる。
実はこれは単にフィボナッチ数列の第N項の値を一致する。
Nが非常に大きくDPで第N項を求めることができないので、行列累乗を用いよう。
2^Nから0になる組み合わせを引けば1になる組み合わせの数を求められる。
あとはKの各桁の0/1に応じ、前記組み合わせの積を取ればよい。
ll N,K,L,mo; ll dp[101010][2],sp0,sp1; map<ll,ll> D; const int MAT=2; ll G[MAT][MAT],G2[MAT][MAT]; void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) { int i,x,y,z; ll a2[MAT][MAT]; FOR(x,n) FOR(y,n) a2[x][y]=a[x][y]; FOR(x,n) FOR(y,n) r[x][y]=0; FOR(i,n) r[i][i]=1; while(p) { ll h[MAT][MAT]; if(p%2) { FOR(x,n) FOR(y,n) h[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo; FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo; } FOR(x,n) FOR(y,n) h[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo; FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo; p>>=1; } } ll modpow(ll a, ll n) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K>>L>>mo; if(L!=64 && K>=(1ULL<<L)) return _P("0\n"); vector<ll> T; G[0][0]=G[0][1]=G[1][0]=1; powmat(N,2,G,G2); sp0=(G2[0][0]+G2[0][1])%mo; sp1=(mo+modpow(2,N)-sp0)%mo; ll pat=modpow(sp1,__builtin_popcountll(K))*modpow(sp0,L-__builtin_popcountll(K))%mo; cout<<pat<<endl; }
まとめ
周り見るとフィボナッチ数列はライブラリしてる人も結構いたね。