题解 CF551D 【GukiZ and Binary Operations】
swiftc
2019-08-01 07:49:31
## 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;
}
```