題目鏈接：

https://www.codechef.com/problems/LEMOVIE

對(duì)于這種類(lèi)似排列，并且有大小關(guān)系的貢獻(xiàn)，一般要按從大到小或從小到大插入進(jìn)行討論

一組數(shù)有貢獻(xiàn)當(dāng)且僅當(dāng)至少一個(gè)數(shù)被插到了最前面，那么就分情況進(jìn)行討論即可

就是插板法，把y個(gè)數(shù)插到x個(gè)數(shù)當(dāng)中，把x個(gè)數(shù)之間的空隙看成盒子

因?yàn)槭桥帕?#xff0c;所以插完以后還要乘一下階乘

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<cmath> using namespace std; typedef long long ll;const int maxn = 210; const int mod = 1e9+7;int T,n,m,q; int a[maxn],b[maxn],c[maxn]; int f[maxn][maxn]; int C[1010][1010],jc[1010];bool cmp(int a,int b){return a>b; }ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}int main(){T=read();jc[0]=1;for(int i=1;i<=1000;i++) jc[i]=1ll*jc[i-1]*i%mod;C[0][0]=1;for(int i=1;i<=1000;i++){C[i][0]=C[i][i]=1;for(int j=1;j<i;j++){C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}} while(T--){q=0;memset(f,0,sizeof(f)); n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(a[i]!=a[i-1]){b[++q]=a[i];c[q]=1;}else{++c[q];}}f[0][0]=1; int cnt=0;for(int i=1;i<=q;i++){for(int j=1;j<=m;j++){f[i][j]=(1ll*f[i-1][j]*jc[c[i]]%mod*C[c[i]+cnt-1][cnt-1]%mod+1ll*f[i-1][j-1]*jc[c[i]]%mod*C[c[i]+cnt-1][cnt]%mod)%mod;}cnt+=c[i];}int ans=0;for(int i=1;i<=m;i++) ans=(ans+f[q][i])%mod;printf("%d\n",ans);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/tuchen/p/10439705.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的codechef LEMOVIE dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。