题解 CF551D 【GukiZ and Binary Operations】

swiftc

2019-08-01 07:49:31

Solution

## Solution: 我们将 k 按二进制位考虑: 设$f[i][0]$为k的二进制位第$i$位为0时这一位的方案数,$f[i][1]$为k的二进制位第$i$位为1时这一位的方案数 对于 k 的每一位,如果为 0,那么每个 $and$ 的两个数的二进制最后一位一定不能均为 1, 由此得出转移方程: $f [ i ] [ 0 ] = f [ i - 1 ] [ 1 ] + f [ i - 1 ] [ 0 ]$ $f [ i ] [ 1 ] = f [ i - 1 ] [ 0 ]$ 因为这两个式子联立,所以$f[i][0]$显然是斐波那契数列,所以当 k 的一个二进制位为 0 时,可以用矩阵快速幂求出斐波那契数列的第 n+1 项,即为答案 如果为 1,至少有一个 $and$ 中的两个数的二进制最后一位均为 1, 所以我们可以用总方案数减去 k 位为 0 的情况的方案数,也就是 $2 ^ n - f [ n + 1 ]$,最后乘法原理把结果乘起来即可 ## CODE: ```cpp #include<bits/stdc++.h> #define int unsigned long long using namespace std; int n,k,l,m; struct node{ int a[3][3]={{0,0,0},{0,0,0},{0,0,0}}; node operator *(const node &t) { node tmp; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) { for(int k=1;k<=2;k++) { tmp.a[i][j]+=(a[i][k]*t.a[k][j])%m; tmp.a[i][j]%=m; } } return tmp; } }; int fib(int num){ //矩阵加速求斐波那契数列第n项 node m,ans; m.a[1][1]=1; m.a[1][2]=1; m.a[2][1]=1; ans.a[1][1]=1; ans.a[2][2]=1; while(num){ if(num&1){ ans=ans*m; } m=m*m; num/=2; } return ans.a[1][1]; } int count_bit(int x) { int bit = 0; if(x == 0) return 1; while(x) { bit++; x >>= 1; } return bit; } int qpow(int a,int b){ if(b==0)return 1; int tmp=qpow(a,b/2); return b%2?tmp*tmp%m*a%m:tmp*tmp%m; } main(){ int ans=1,fb,hp; cin>>n>>k>>l>>m; if(l<=62&&k>=(1LL<<l)) { //判断结果是否为0,记得用1LL puts("0"); return 0; } int bit[1000],cnt=0; while(k){ bit[++cnt]=k%2; k>>=1; //分解二进制位 } fb=fib(n+1); hp=(qpow(2,n)+m-fib(n+1))%m; for(int i=1;i<=l;i++){ if(bit[i]==1){ ans*=hp; ans%=m; } else{ ans*=fb; ans%=m; } } printf("%llu",ans%m);//记得再%一次m,不然会WA return 0; } ```