題目地址：http://codeforces.com/contest/551/problem/D
分析下公式能夠知道，相當(dāng)于每一位上放0或者1使得最后成為0或者1。假設(shè)最后是0的話，那么全部相鄰位一定不能全是1，由于假設(shè)有一對相鄰位全為1，那么這兩個的AND值為1。又由于OR值是僅僅要有1。結(jié)果就為1。所以這位結(jié)果肯定為1。所以就推出了一個dp轉(zhuǎn)移方程。dp[i][j]表示第i位上的數(shù)為j時的總個數(shù)。那么有：
dp[i][0]=dp[i-1][0]+dp[i-1][1];
dp[i][1]=dp[i-1][0];
設(shè)f[i]表示第i位上的總個數(shù)，即f[i]=dp[i][0]+dp[i][1].
所以，f[i]=dp[i-1][0]+dp[i-1][1]+dp[i-1][0]
f[i]=f[i-1]+dp[i-1][0]
f[i]=f[i-1]+dp[i-2][0]+dp[i-2][1]
f[i]=f[i-1]+f[i-2]
所以，推到最后可發(fā)現(xiàn)這是一個斐波那契！！

所以用矩陣高速冪求結(jié)果為0時的情況。然后為1的時候就是2^n-（結(jié)果為0的情況值）。

然后由于每一位都是獨立的，所以分別推斷每一位是0還是1，然后乘起來。

代碼例如以下：

#include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib.h> #include <map> #include <set> #include <stdio.h> #include <time.h> using namespace std; #define LL __int64 #define pi acos(-1.0) //#pragma comment(linker, "/STACK:1024000000") //const int mod=9901; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=110000+10; LL mod; struct Matrix {LL ma[3][3]; }init,res; LL ksm(LL k, LL x) {LL ans=1;while(k){if(k&1) ans=ans*x%mod;k>>=1;x=x*x%mod;}return ans; } Matrix Mult(Matrix x, Matrix y, int z) {Matrix tmp;for(int i=0; i<z; i++) {for(int j=0; j<z; j++) {tmp.ma[i][j]=0;for(int k=0; k<z; k++) {tmp.ma[i][j]+=x.ma[i][k]*y.ma[k][j];if(tmp.ma[i][j]>=mod) tmp.ma[i][j]%=mod;}}}return tmp; } Matrix Pow(Matrix x, LL k, int z) {Matrix tmp;int i, j;for(i=0; i<z; i++) for(j=0; j<z; j++) tmp.ma[i][j]=(i==j);while(k) {if(k&1) tmp=Mult(tmp,x,z);x=Mult(x,x,z);k>>=1;}return tmp; } int main() {LL n, k, l, x1, x2, ans, tmp, i;while(scanf("%I64d%I64d%I64d%I64d",&n,&k,&l,&mod)!=EOF){if(l<=62&&k>=((LL)1<<l)){puts("0");continue ;}init.ma[0][0]=init.ma[0][1]=1;init.ma[1][0]=1;init.ma[1][1]=0;res=Pow(init,n-2,2);tmp=ksm(n,(LL)2);x1=(res.ma[0][1]*2%mod+res.ma[0][0]*3%mod)%mod;x2=(tmp+mod-x1)%mod;ans=1;for(i=0;i<l;i++){if(k&((LL)1<<i))ans=ans*x2%mod;else ans=ans*x1%mod;}printf("%I64d\n",ans%mod);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cxchanpin/p/7264107.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #307 (Div. 2) D. GukiZ and Binary Operations （矩阵高速幂）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。