swift's blog

swift's blog

题解 CF551D 【GukiZ and Binary Operations】

posted on 2019-08-01 07:49:31 | under 题解 |

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:

#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;
}