#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; }
2015年7月2日 星期四
Codeforces Round #307 (Div. 2), problem: (D) GukiZ and Binary Operations
以前碰到的題目好像都有保證m > 1之類,看來以後要多注意._.
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言