00:00/00:00

1000:DistinctRemainders

题意:

给你两个数,N和M,要求你找到一个数的序列,所有数对M取模互不相同,然后所有数的和为N。。。输出所有可能数。。。

分析:

因为每一个余数只能取一次,那我们写一个背包,表示取i个数后,和为j的种类数,然后考虑贡献就是当前值乘上把多余的数(N-j)分给他们的种类。。。

代码:

LL A(LL n,int m)
{
    if (n<m) return 0;
    LL ans=1;
    for(int i=1;i<=m;i++)
     ans=ans*((n-i+1)%mod)%mod;
    return ans;
}
int dp[55][2550];
LL ans;
int DistinctRemainders::howMany(long long N, int M) 
{
    int maxn=0;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=0;i<M;i++)
    {
        maxn+=i;
        for(int j=i+1;j;j--) 
            for(int k=i;k<=maxn;k++)
                (dp[j][k]+=dp[j-1][k-i]%mod)%=mod;
    }
    ans=1;
    for(int i=2;i<=M;i++)
        for(int j=0;j<=maxn;j++)
            if((j%M)==(N%M))
            {
                LL flag=(N-j)/M;
                (ans+=dp[i][j]*(A(flag+i-1,i-1)%mod*i%mod))%=mod;
            }
    return ans;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注