mayoko’s diary

プロコンとかいろいろ。

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;
}