Pinely Round 1 (Div. 1 + Div. 2)--D

D. Carry Bit

思路

首先时分堆，也就是把小球放进盒子的问题，然后进行讨论

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int M=1e6+5,mod=1e9+7;

int kpow(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

int fact[M],infact[M],a[M];
void init(int n=1e6) {
    fact[0]=infact[0]=a[0]=1;;
    for(int i=1;i<=n;i++) {
        fact[i]=fact[i-1]*i%mod;
        infact[i]=kpow(fact[i],mod-2);
        a[i]=a[i-1]*3%mod;
    }
}

int C(int a,int b) {
    return fact[a]*infact[b]%mod*infact[a-b]%mod;
}

signed main() {
    int n,k;
    cin>>n>>k;
    init();
    if(k==0)cout<<a[n]<<'\n';
    else {
        int ans=0;
        for(int i=1;i<=k;i++) {//要选的堆的数量
            int j=k+i;//需要的位置
            //采用隔板法进行计算
            if(j-1<=n)ans=(ans+C(k-1,i-1)*a[n-2*i+1]%mod*C(n-k,i-1)%mod)%mod;
            if(j<=n)ans=(ans+C(k-1,i-1)*a[n-2*i]%mod*C(n-k,i)%mod)%mod;
            //隔板法求放的种类,然后对剩下的进行相乘，还要对箱子的位置进行排序
        }
        cout<<ans<<'\n';
    }
    return 0;
}