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

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

拉格朗日插值的时候明明是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;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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