题解：CF2072F Goodbye, Banker Life

· · 题解

转化为奇偶判定 + Lucas 定理

首先不难发现 f_{i,j} 的取值只可能是 0 或 k，不妨把 k 看作 1。那么通过 f_{i,j} 的奇偶性即可确定 f_{i,j} 的值。

由于异或的本质为二进制下的不进位加法，故可以把 f_{i,j}=f_{i-1,j-1} \oplus f_{i-1,j} 转换为 f_{i,j}=f_{i-1,j-1} + f_{i-1,j}，并把问题转换为判断 f_{i,j} 的奇偶性。

注意到转换后的 f_{i,j} 是杨辉三角。

对于杨辉三角：

由于行号和列号规定均从 1 开始计数，因此对于 f_{i,j}，它的值就是 \binom{i-1}{j-1} 的值。

那么显然可以用 Lucas 定理秒了。回顾 Lucas 定理：

\binom{i}{j} \equiv \binom{\lfloor \frac{i}{p} \rfloor}{\lfloor \frac{j}{p} \rfloor} \times \binom{i \bmod p }{j \bmod p } \pmod p

那么最终输出第 n 行的第 j 个数时，即输出 \operatorname{lucas}(n-1,j) \times k。

int n,k;
int fastpow(int a,int n,int mod){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
int getC(int n,int m,int mod){
    int res=1;
    for(int i=n,j=1;j<=m;i--,j++){
        res=res*i%mod;
        res=res*fastpow(j,mod-2,mod)%mod;
    }
    return res;
}
int lucas(int n,int m,int p){
    if(!m) return 1;
    return lucas(n/p,m/p,p)*getC(n%p,m%p,p);
}
void solve(){
    cin>>n>>k;
    rep(i,1,n) cout<<lucas(n-1,i-1,2)*k<<" ";
}

此外还有一个结论做法：

当 \bmod=2 时有一个结论，\binom{n}{m} 等价于 n \& m ==m。

也就是说代码还可以这样写：

int n,k;
int calc(int n,int m){
    return (n&m)==m;
}
void solve(){
    cin>>n>>k;
    rep(i,1,n) cout<<calc(n-1,i-1)*k<<" ";
}