1453?抽彩球

?

題目來源：?CodeForces 基準(zhǔn)時間限制：1?秒 空間限制：131072?KB 分值:?40?難度：4級算法題 ?收藏 ?關(guān)注

一個袋子中有n個彩球，他們用k種不同的顏色染色。顏色被從1到k編號。同一種顏色的球看成是一樣的?，F(xiàn)在從袋中一個一個的拿出球來，直到拿完所有的球。對于所有顏色為i (1<=i<=k-1)的球，他的最后一個球總是在編號比他大的球拿完之前拿完，問這樣情況有多少種。

樣例解釋：這個樣例中有2個1號顏色的球，2個2號顏色的球，1個3號顏色的球。三種方案是：
1 2 1 2 3
1 1 2 2 3
2 1 1 2 3

Input 單組測試數(shù)據(jù)。 第一行給出一個整數(shù)k(1?≤?k?≤?1000)，表示球的種類。 接下來k行，每行一個整數(shù)ci,表示第i種顏色的球有ci個(1?≤?ci?≤?1000)。 球的總數(shù)目不超過1000。 Output 輸出總數(shù)對1,000,000,007的模即可。 Input示例 3 2 2 1 Output示例 3

正著放球有許多限制 我們很難求解
我們可以考慮反著放
題目要求 你想放最后一個種類為2的球 那么你種類為1的球一定已經(jīng)全部放在這最后一個種類為2的球的前面位置 (看著樣例理解)
對于第i個 球我們一定會在最后一個空位置放一個 然后其他的可以在前面的空位置隨便放
就是 C(空位置數(shù)量，c[i]-1)

對于第i-1種球 我們要先在最后一個空位置放一個 其他再往前放
.
.
.

可以發(fā)現(xiàn)
這就是求一個組合數(shù)C(n,m) 由于 n，m 在10^6左右
我們可以用Lucas定理
Lucas定理 C(n,m)%p(p為素數(shù)) C(n,m)與C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余 a,b 是n，m在p進(jìn)制下的數(shù) 有的推公式： (C(n%p,m%p,p)*Lcs(n/p,m/p,p))%p; 關(guān)鍵是求 C(n%p,m%p,p) 遞歸會很慢 for的話會爆掉 這里用一個定理：a/b%p <--> a*x%p x為b在b%p下的逆元 再來一個定理：x=b^(p-2) x為b在%p下的逆元 p為素數(shù) 然后預(yù)處理一下階乘就ok了 ? 1 #include <cctype> 2 #include <cstdio> 3 4 typedef long long LL; 5 6 const int mod=1e9+7; 7 const int MAXN=1000010; 8 9 int n,sum; 10 11 int c[MAXN]; 12 13 LL fact[MAXN]; 14 15 inline void read(int&x) { 16 int f=1;register char c=getchar(); 17 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 18 for(;isdigit(c);x=x*10+c-48,c=getchar()); 19 x=x*f; 20 } 21 22 inline LL quick_pow(LL a,LL k) { 23 LL ret=1; 24 while(k) { 25 if(k&1) ret=(ret*a)%mod; 26 k>>=1; 27 a=(a*a)%mod; 28 } 29 return ret%mod; 30 } 31 32 inline LL C(int a,int b) { 33 return fact[a]*quick_pow(fact[b]*fact[a-b]%mod,mod-2)%mod; 34 } 35 36 inline void Factorial() { 37 fact[0]=1; 38 for(int i=1;i<=MAXN;++i) 39 fact[i]=(fact[i-1]*i)%mod; 40 } 41 42 int hh() { 43 Factorial(); 44 read(n); 45 for(int i=1;i<=n;++i) read(c[i]),sum+=c[i]; 46 LL ans=1; 47 for(int i=n;i;--i) { 48 ans=(ans*C(sum-1,c[i]-1))%mod; 49 sum-=c[i]; 50 } 51 printf("%lld\n",ans); 52 return 0; 53 } 54 55 int sb=hh(); 56 int main(int argc,char**argv) {;} 代碼

?

?

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

總結(jié)

以上是生活随笔為你收集整理的51Nod 1453 抽彩球的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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