CF1761D Carry Bit 题解

· · 题解

首先很显然有一个 \mathcal{O}\left(nk\right) 的朴素 DP 做法，具体地设 dp_{i,j,0/1} 表示当前考虑了前 i 位，进位了 j 次，并且 i 位上是否向 i+1 进位的方案数。考虑刷表计算，从 dp_{i,j,0/1} 向下推，分类讨论一下第 i+1 位两个数的情况可以得到：

最终答案是 dp_{n,k,0} 或者 dp_{n,k-1,1}。发现可以重新给这个 DP 式子一个组合意义：有一个变量 x=0，每次有三种操作将 x 异或上 1，一种操作异或上 0，然后任意操作 n，让每个时刻的 x 的状态构成一个长度为 n+1 的 01 序列，答案就是有多少中操作方案使得最终序列里面有 k 个 1。枚举 x 变化的总次数 i，那么 01 串中有 \lceil\frac{i}{2}\rceil 个 0 的连续段，\lfloor\frac{i}{2}\rfloor 个 1 的连续段，0 连续段的总长必须为 n+1−k，1 连续段的总长必须为 k，用插板法计算方案数。

MODINT::MODNUM pw3[2000010];

#define PC_DATA_TYPE long long

const PC_DATA_TYPE PC_MOD=1000000007;
const PC_DATA_TYPE PC_DATA_SIZE=2000010;

PC_DATA_TYPE inv[PC_DATA_SIZE],fact[PC_DATA_SIZE],invfact[PC_DATA_SIZE];

void init_pc(int n){
    register int i;
    for(inv[0]=0,inv[1]=fact[0]=fact[1]=invfact[0]=invfact[1]=1,i=2;i<=n;++i)
        invfact[i]=invfact[i-1]*(inv[i]=PC_MOD-PC_MOD/i*inv[PC_MOD%i]%PC_MOD)%PC_MOD,fact[i]=fact[i-1]*i%PC_MOD;
    return;
}

PC_DATA_TYPE A(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return fact[n]*invfact[n-m]%PC_MOD;
}
PC_DATA_TYPE C(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return fact[n]*invfact[n-m]%PC_MOD*invfact[m]%PC_MOD;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    MODINT::init(1000000007);

    register int i;
    register MODINT::MODNUM res=0;
    int n=read();
    int k=read();

    init_pc(n*2);
    for(i=pw3[0]=1;i<=n*2;++i) pw3[i]=pw3[i-1]*3;

    if(k==0) return print(pw3[n]),0;

    for(i=1;i<=k;++i){
        if(n-i*2>=0) res+=pw3[n-i*2]*C(n-k,i)*C(k-1,i-1);
        if(n-i*2+1>=0) res+=pw3[n-i*2+1]*C(n-k,i-1)*C(k-1,i-1);
    }

    print(res);

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}