P3270 [JLOI2016]成绩比较（容斥+自然数幂和）

· · 题解

P3270 [JLOI2016]成绩比较

由容斥原理得：

ans=\sum_{i=K}^{\min\{N-R\}}(-1)^{i-K}C_i^KC_{N-1}^i\prod_{j=1}^MC_{N-1-i}^{N-R_j-i}\sum_{x=1}^{U_j}x^{N-R_j}(U_j-x)^{R_j-1}

这个很长的式子表示：分别求至少有 i 个人被碾压的方案数，然后容斥一下；从 n-1 个人里选 i 个被碾压；对每门课考虑有多少人这门课这门课被碾压；枚举 B 神的成绩，算这门课被碾压的人的成绩的情况数及碾压 B 神的人的成绩的情况数。

由于 U_i 太大，(U_j-x)^{R_j-1} 不好处理。可以暴力展开

\begin{aligned}\sum_{x=1}^{U_j}x^{N-R_j}(U_j-x)^{R_j-1}=&\sum_{x=1}^{U_j}x^{N-R_j}\sum_{k=0}^{R_j-1}{R_j-1\choose k}(-1)^kx^kU_j^{R_j-1-k}\\=&\sum_{k=0}^{R_j-1}{R_j-1\choose k}(-1)^kU_j^{R_j-1-k}\sum_{x=1}^{U_j}x^{N-R_j+k}\end{aligned} 复杂度 $O(n^2m)

不是很长的代码不知道为啥写了一个小时。抄不对式子啊（捂脸）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m,K;
    const int N=110,mo=1e9+7;
    int U[N],R[N],B[N],C[N][N],S[N][N],inv[N],mn=10000,ans;
    void work()
    {
        scanf("%d%d%d",&n,&m,&K);
        for(int i=1;i<=m;i++)
            scanf("%d",&U[i]);
        for(int i=1;i<=m;i++)
            scanf("%d",&R[i]),mn=min(mn,n-R[i]);
        for(int i=0;i<=n;i++)
        {
            C[i][0]=1;
            for(int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
        }
        inv[0]=inv[1]=B[0]=1;
        for(int i=2;i<=max(n,m)+5;i++)
            inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
        for(int i=1;i<=n;i++)
            for(int j=0;j<i;j++)
                B[i]=(B[i]-1ll*B[j]*inv[i-j+1]%mo*C[i][j]%mo+mo)%mo;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                int sum=0;
                for(int k=j,s=U[i]+1;k>=0;k--,s=1ll*s*(U[i]+1)%mo)
                    sum=(sum+1ll*C[j+1][k]*B[k]%mo*s%mo)%mo;
                S[i][j]=1ll*inv[j+1]*sum%mo;
            }
        for(int i=K;i<=mn;i++)
        {
            int tmp=1ll*((i-K)&1?mo-1:1)*C[i][K]%mo*C[n-1][i]%mo,s=1;
            for(int j=1;j<=m;j++)
            {
                int sum=0;
                for(int k=R[j]-1,tmp=1;k>=0;k--,tmp=1ll*tmp*U[j]%mo)
                    sum=(sum+1ll*((k&1)?mo-1:1)*tmp%mo*S[j][n-R[j]+k]%mo*C[R[j]-1][k]%mo)%mo;
                s=1ll*s*C[n-1-i][n-R[j]-i]%mo*sum%mo;
            }
            ans=(ans+1ll*tmp*s%mo)%mo;  
        }
        printf("%d\n",ans);
    }
}
int main()
{
    FGF::work();
    return 0;
}