2015年7月2日 星期四

Codeforces Round #307 (Div. 2), problem: (D) GukiZ and Binary Operations

以前碰到的題目好像都有保證m > 1之類,看來以後要多注意._.


#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

int64 n, k, m;

int64 mul(int64 a, int64 b){
    return (a*b)%m;
}

int64 Pow(int64 a, int64 n){
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 P = Pow(a, n>>1);
    P = mul(P, P);
    if(n&1) return mul(P, a);
    return P;
}

struct Mat{
    int64 a, b, c, d;
    Mat(int64 _a = 1, int64 _b = 0, int64 _c = 0, int64 _d = 1):
        a(_a%m), b(_b%m), c(_c%m), d(_d%m){return;}
};

Mat operator*(Mat& s, Mat& t){
    return Mat(mul(s.a,t.a) + mul(s.b,t.c),
               mul(s.a,t.b) + mul(s.b,t.d),
               mul(s.c,t.a) + mul(s.d,t.c),
               mul(s.c,t.b) + mul(s.d,t.d));
}

Mat Pow(Mat a, int64 n){
    if(n == 0) return Mat();
    if(n == 1) return Mat(a);
    Mat P = Pow(a, n>>1);
    P = P*P;
    if(n&1) return P*a;
    return P;
}

int main(){
    int l;
    scanf("%I64d %I64d %d %I64d", &n, &k, &l, &m);
    int64 ans = 1%m;
    Mat gg(Pow(Mat(0, 1, 1, 1), n-2));
    // b1 = 2, b2 = 3, b3 = 5
    int64 bb = (3*gg.a+5*gg.b)%m;
    int64 aa = (Pow(2, n)-bb+m)%m;
    for(int lx = 0;lx < l;lx++){
        if(k&1) ans = mul(ans, aa); 
        else ans = mul(ans, bb);
        k>>=1;
    }
    if(k) ans = 0;
    printf("%I64d\n", ans);
    return 0;
}

沒有留言:

張貼留言