2015年7月31日 星期五

2015/07/31 Codeforces 551D. GukiZ and Binary Operations

/*
    費氏數列
    快速冪

    special case好多 =3=
*/
// http://codeforces.com/contest/551/problem/D
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int MOD;

struct matrix
{
    static const int n = 2;
    int A[n][n];

    matrix()
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                A[i][j] = 0;
    }

    matrix operator*(const matrix &p) const
    {
        matrix R = matrix();

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    R.A[i][k] += (ll)A[i][j]*p.A[j][k]%MOD,
                    R.A[i][k] %= MOD;

        return R;
    }
};

matrix eye, fab;

matrix pwd(matrix &x, ll n)
{
    if( n == 0 ) return eye;

    matrix p = pwd(x, n/2);
    if( n&1 ) return p*p*x;
    else return p*p;
}

int pwd(int x, ll n)
{
    if( n == 0 ) return 1;

    int p = pwd(x, n/2);
    if( n&1 ) return (ll)p*p%MOD*x%MOD;
    else return (ll)p*p%MOD;
}

ll N, K; int L;

int main()
{
    eye.A[0][0] = 1; eye.A[0][1] = 0;
    eye.A[1][0] = 0; eye.A[1][1] = 1;

    cin>>N>>K>>L>>MOD;

    if( L == 0 && K == 0 ){ printf("%d\n", 1%MOD); return 0; }
    else if( L == 0 || K/2 >= (1ULL<<L-1) ){ puts("0"); return 0; }

    fab.A[0][0] = 1; fab.A[0][1] = 1;
    fab.A[1][0] = 1; fab.A[1][1] = 0;

    matrix A = pwd(fab, N);

    int zero = (A.A[0][0]+A.A[0][1])%MOD;
    int one = ((pwd(2, N)-zero)%MOD+MOD)%MOD;

    int Ans = 1;

    for(unsigned long long Li = 0, val = 1; Li < L; Li++, val<<=1)
        if( K&val ) Ans = (ll)Ans*one%MOD;
        else Ans = (ll)Ans*zero%MOD;

    cout<<Ans<<endl;
}

沒有留言:

張貼留言