题解：CF232B Table

题目大意

已经很清楚了。

思路分析

发现列数非常有趣，并且数点的正方形在垂直于列的方向移动，考虑从每一列入手。
令

col_i

为第

i

列的点数，我们滑动一下数点的正方形，立刻就能发现

col_{i+n}=col_i

。

于是这里有一个周期，每当我们确定了某一列的点数，就可以立刻确定之后所有模

n

同余的列的点数，然后直接计算贡献，即

\binom{n}{col_i}^{\frac{m-i}{n}+1}

。

现在的问题变成了数的分解，这里可以把快速幂预处理，搞一个

O(n^2k)

的 dp，如果懒得预处理，也可以用 ull 的小常数直接卡过去。

代码展示

CPP

#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;

const int mod=1e9+7;
int n,k;
ll m;
ll frac[200],invfrac[200],dp[105][10050];

ll qpow(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=res*x%mod;
        p>>=1;
        x=x*x%mod;
    }
    return res;
}

ll C(int n,int m){
    return frac[n]*invfrac[m]%mod*invfrac[n-m]%mod;
}

int main(){
    cin>>n>>m>>k;
    frac[0]=1;
    for(int i=1;i<=n;i++)frac[i]=i*frac[i-1]%mod;
    invfrac[n]=qpow(frac[n],mod-2);
    for(int i=n-1;i>=0;i--)invfrac[i]=invfrac[i+1]*(i+1)%mod;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            int ww=qpow(C(n,j),(i<=(m-1)%n+1)?(m-1)/n+1:(m-1)/n)%mod;
            for(int t=j;t<=min(i*n,k);t++){
                dp[i][t]=(dp[i][t]+dp[i-1][t-j]*ww%mod)%mod;
            }
        }
    }
    cout<<dp[n][k];
    return 0;
}

文章操作

题目大意

思路分析

代码展示

相关推荐

评论

题解：CF232B Table