問題 B: yoyo思維題(困難)

時(shí)間限制:?1 Sec??內(nèi)存限制:?256 MB
提交:?11??解決:?3
[提交][狀態(tài)][討論版][命題人:qianyouyou][Edit] [TestData]

題目描述

小琳，小花，小薇，yoyo，他們每個(gè)人手上有一堆牌，牌的張數(shù)分別為x1，x2，x3，x4，每張牌都不一樣。現(xiàn)有n名同學(xué)，n=x1+x2+x3+x4。每名同學(xué)均需要一張牌，于是他們按順序每人隨機(jī)到四個(gè)人那里拿取牌頂?shù)囊粡埮?#xff0c;最后一個(gè)人剛好拿到剩下的最后一張牌。排隊(duì)拿牌的同學(xué)的順序是固定的，選擇拿誰(shuí)的牌是不確定的。假如發(fā)牌的人手上的牌發(fā)完了，則要拿牌的同學(xué)會(huì)選擇其他發(fā)牌的人。請(qǐng)問有多少種取法取走所有的牌。

輸入

首行輸入t，代表t組測(cè)試樣例

對(duì)于每一行，輸入四個(gè)整數(shù)a，b，c，d，輸入為均不超過500的正整數(shù)

輸出

對(duì)于每組樣例，輸出一個(gè)整數(shù)表示答案，答案對(duì)10^9+7取模

樣例輸入

1 5 4 2 3

樣例輸出

2522520

提示

本題作為思維題，并未用到stl，僅鍛煉一下大家解決問題的能力。用到的數(shù)學(xué)知識(shí)相對(duì)多一點(diǎn)。

題解

題目大致可以理解為4堆牌a,b,c,d，每次從一堆牌里拿出牌頂?shù)囊粡埮?#xff0c;問共有多少種拿法。

其實(shí)我們可以一堆一堆的分析，假設(shè)只有一堆a(bǔ)時(shí)，只有1種拿法，

那兩堆a(bǔ),b時(shí)我們可以認(rèn)為是從a個(gè)牌中插入b張牌，用數(shù)學(xué)表達(dá)式就是C(b,a+b);

那么三堆的話我們可以把前兩堆看成一堆，那么表達(dá)式就是C(c,a+b+c)，

這是我們需要與前兩堆的組成方法相乘，就是C(b,a+b)C(c,a+b+c)。

4堆的話就是C(b,a+b)C(c,a+b+c)C(d,a+b+c+d)。所以答案就是C(a,a)C(b,a+b)C(c,a+b+c)C(d,a+b+c+d)。

此外，有一公式C(a,b) = C(a,b-1)+C(a-1,b-1)，所以我們用數(shù)組來(lái)代替C(m,n)操作

參考代碼：

#include<iostream> #include<cstring> #define ll long long using namespace std; const int maxn = 501; const ll mod = 1000000007; ll a[4], sum[4] = { 0 }; ll dp[maxn * 4][maxn * 4]; //打表，遞推公式C(a,b) = C(a,b-1)+C(a-1,b-1) void init() {dp[0][0] = 0;for (int i = 1; i < 4 * maxn; i++) {dp[i][0] = 1;for (int j = 1; j < i; j++) {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];dp[i][j] %= mod;}dp[i][i] = 1;} } int main() {int t;cin>>t;while(t--){init();//打表ll ans = 1;//這一步可要可不要，其實(shí)就是將a,a+b,a+b+c,a+b+c+d存進(jìn)sum里for (int i = 0; i < 4; i++) {!i ? sum[i] = 0 : sum[i] = sum[i - 1];cin >> a[i];sum[i] += a[i];if (a[i] > sum[i] - a[i]) a[i] = sum[i] - a[i];}//將對(duì)應(yīng)3組排列組合相乘，及C(b,a+b)C(c,a+b+c)C(d,a+b+c+d)for (int i = 1; i < 4; i++) {ans *= dp[sum[i]][a[i]];ans %= mod;}cout << ans << endl;}return 0; }

自己寫的代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=510,mod=1e9+7; ll mp[maxn*4][maxn*4];int main() {mp[0][0]=0;for(int i=1;i<=2000;i++)mp[i][1]=i;for(int i=1;i<=2000;i++)for(int j=2;j<=2000;j++)mp[i][j]=((mp[i-1][j])%mod+(mp[i-1][j-1])%mod)%mod; /*for(int i=1;i<=50;i++){for(int j=1;j<=50;j++){printf("%d ",mp[i][j]);}printf("\n");} */int T;cin>>T;while(T--){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);printf("%d\n",(((mp[a+b][b]%mod)*(mp[a+b+c][c]%mod))%mod*(mp[a+b+c+d][d]%mod))%mod);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的yoyo思维题(困难) 组合数学的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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