Codeforces Round #307 (Div. 2) D. GukiZ and Binary Operations
いや簡単だったか…
解法
kを2進数表示した際の各桁が0/1になる場合の数を考える。
0になる場合の数が簡単なのでそっちを考える(これを数えることができると1になる場合の数は2^n-(0になる場合の数)と求めることができる)。
p[n]を配列aのn番目まで考慮した時の(a[0]&a[1])|...|(a[n-1]&a[n])が0になる場合の数とする。
a[n]が1であるとすると,a[n-1]は0でなければならない。a[n-2]からは好きに決めて良いのでp[n-2]通り。
a[n]が0であるとすると,a[n-1]は何でも良いのでp[n-1]通り。
よって,p[n] = p[n-1]+p[n-2]となり,フィボナッチ数列っぽっく行列累乗をすれば良い。
typedef long long number; typedef vector<number> vec; typedef vector<vec> matrix; ll MOD = 1e9+7; // O( n ) matrix identity(int n) { matrix A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n^3 ) matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), vec(B[0].size())); for (int i = 0; i < (int)C.size(); ++i) for (int j = 0; j < (int)C[i].size(); ++j) for (int k = 0; k < (int)A[i].size(); ++k) { C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } return C; } // O( n^3 log e ) matrix pow(const matrix &A, ll e) { if (e == 0) return identity(A.size()); if (e == 1) return A; if (e % 2 == 0) { matrix tmp = pow(A, e/2); return mul(tmp, tmp); } else { matrix tmp = pow(A, e-1); return mul(A, tmp); } } ll pow_mod(ll x, ll p, ll m) { if (x == 0) return 0; if (p == 0) return 1; if (p%2) return (x*pow_mod(x, p-1, m)) % m; else { ll tmp = pow_mod(x, p/2, m); return (tmp*tmp)%m; } } int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, k, l, m; cin >> n >> k >> l >> m; MOD = m; if (l != 64 && (k>>l) > 0) { cout << 0 << endl; return 0; } ll p2 = pow_mod(2, n, m); matrix A(2, vec(2)); A[0][0] = A[0][1] = A[1][0] = 1; A = pow(A, n-2); ll pn = (A[0][0]*3+A[0][1]*2)%m; ll rest = (p2-pn+m)%m; ll ans = 1; for (int i = 0; i < l; i++) { if ((k>>i)&1) { ans *= rest; } else { ans *= pn; } ans %= m; } cout << ans%m << endl; return 0; }