很不错的一道数数题.
code:
#include <cstdio> #include <algorithm> #define N 203 #define ll long long #define mod 1000000007 #define setIO(s) freopen(s".in","r",stdin) using namespace std; int n,m,kth; int ui[N],ri[N],f[N],g[N][N],h[N][N],fac[N],inv[N]; int qpow(int x,int y) { int tmp=1; for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) tmp=(ll)tmp*x%mod; return tmp; } int INV(int x) { return qpow(x,mod-2); } void Initialize() { int i,j; fac[0]=inv[0]=1; for(i=1;i<N;++i) fac[i]=(ll)fac[i-1]*i%mod,inv[i]=INV(fac[i]); } int C(int x,int y) { if(x<0||y<0||x<y) return 0; return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod; } int main() { int i,j,ans=0; // setIO("input"); Initialize(); scanf("%d%d%d",&n,&m,&kth); for(i=1;i<=m;++i) scanf("%d",&ui[i]); for(i=1;i<=m;++i) scanf("%d",&ri[i]); for(i=0;i<n;++i) { f[i]=C(n-1,i); for(j=1;j<=m;++j) f[i]=1ll*f[i]*C(n-1-i,ri[j]-1)%mod; } for(i=kth;i<=n-kth-1;++i) { (ans+=1ll*((i-kth)%2==0?1:mod-1)*f[i]%mod*C(i,kth)%mod)%=mod; } for(i=1;i<=m;++i) { for(j=1;j<=min(n,ui[i]);++j) { for(int k=1;k<=j;++k) { (g[i][j]+=(ll)qpow(k,n-ri[i])*qpow(j-k,ri[i]-1)%mod)%=mod; } } } for(i=1;i<=m;++i) { int re=0,tmp=ui[i],fa=1; for(j=1;j<=min(n,ui[i]);++j) { h[i][j]=g[i][j]; for(int k=1;k<=j-1;++k) { (h[i][j]+=mod-((ll)h[i][k]*C(j,k)%mod))%=mod; } fa=(ll)fa*tmp%mod*INV(j)%mod; (re+=(ll)fa*h[i][j]%mod)%=mod; --tmp; } ans=(ll)ans*re%mod; } printf("%d\n",ans); return 0; }