P3270 [JLOI2016]成绩比较 容斥 数论 组合数学 拉格朗日插值

LINK：成绩比较

大体思路不再赘述 这里只说几个我犯错的地方。

拉格朗日插值的时候 明明是n次多项式 我只带了n个值进去 导致一直GG.

拉格朗日插值的时候 由于是从1开始的 所以分母是\((i-1)!(n-1)\) 但是一直写成i! 心态炸裂。

还有就是 明明是分母 要求逆啊 直接乘 然后人没了。

最后是 关于答案的统计 由于被碾压的同学 每一科分数永远小于B神 所以 可以不考虑顺序的 将成绩分配给他们。

而 没有被碾压的同学 不可以直接分配 对于每一种方案来说 他们都是可以选择自由分配的 所以需要乘上自由分配的方案。

const int MAXN=110,INV=(mod+1)/2;
int n,m,K;
int U[MAXN],R[MAXN],f[MAXN],w[MAXN];
int fac[MAXN],inv[MAXN],NI[MAXN];
inline int C(int a,int b){return a<b?0:1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;}
inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline int ksm(int b,int p)
{
int cnt=1;
while(p)
{
if(p&1)cnt=(ll)cnt*b%mod;
b=(ll)b*b%mod;p=p>>1;
}
return cnt;
}
inline int lagrange(int n,int x,int op)
{
int ans=1,cnt=0;
if(op)rep(1,n,i)w[i]=(ksm(i,n-2)+w[i-1])%mod,ans=(ll)ans*(x-i)%mod;
else
{
fep(n-1,1,i)w[i]=((ll)w[i]-w[i-1]+mod)*i%mod;
w[n]=ksm(n,n-2);
rep(1,n,i)
{
add(w[i],w[i-1]);
ans=(ll)ans*(x-i)%mod;
}
}
if(x<=n)return w[x];
 add(ans,mod);
rep(1,n,i)
{
int ww=(ll)ans*w[i]%mod;
int cc=(ll)inv[i-1]*inv[n-i]%mod*NI[i]%mod;
add(cnt,(ll)ww*cc%mod*(((n-i)&1)?mod-1:1)%mod);
}
return (cnt+mod)%mod;
}
signed main()
{
freopen("1.in","r",stdin);
get(n);get(m);get(K);K=n-K-1;
rep(1,m,i)get(U[i]);
rep(1,m,i)get(R[i]);
fac[0]=1;rep(1,n+1,i)fac[i]=(ll)fac[i-1]*i%mod,f[i]=1;
inv[n+1]=ksm(fac[n+1],mod-2);f[0]=1;
fep(n,0,i)inv[i]=(ll)inv[i+1]*(i+1)%mod;
int ans=1;
rep(1,m,i)
{
int ww=ksm(U[i],R[i]-1),op=1,cnt=0;
int ni=ksm(U[i],mod-2);
rep(1,n+1,j)NI[j]=ksm((U[i]-j+mod)%mod,mod-2);
rep(0,R[i]-1,k)
{
add(cnt,(ll)ww*op%mod*C(R[i]-1,k)%mod*lagrange(k+n-R[i]+2,U[i],!k)%mod);
ww=(ll)ww*ni%mod;op=mod-op;
}
ans=(ll)ans*cnt%mod;
rep(0,K,j)f[j]=(ll)f[j]*C(j,R[i]-1)%mod;
}
int cc=0;
rep(0,K,j)add(cc,(ll)C(K,j)*f[j]%mod*((K-j)&1?mod-1:1)%mod);
cc=(ll)cc*ans%mod*C(n-1,K)%mod;put(cc);
return 0;
}