Codeforces #307 Div2 D. GukiZ and Binary Operations

ライブラリ化しておこうかなぁ。
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の２値として上式左辺の結果が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;
	
}

まとめ

周り見るとフィボナッチ数列はライブラリしてる人も結構いたね。