現(xiàn)在做網(wǎng)站一般做多寬怎么做微信推廣和宣傳
題目描述:
給定一個多項式?(ax+by)^k,請求出多項式展開后?x^n*y^m 項的系數(shù)。
輸入格式:
共一行,包含?5?個整數(shù),分別為?a,b,k,n,m,每兩個整數(shù)之間用一個空格隔開。
輸出格式:
輸出共?1?行,包含一個整數(shù),表示所求的系數(shù),這個系數(shù)可能很大,輸出對?10007取模后的結果。
數(shù)據(jù)范圍:
0≤n,m≤k≤1000,
n+m=k,
0≤a,b≤1e6;
輸入樣例:
1 1 3 1 2
輸出樣例:
3
分析步驟:
? 第一:理清思路:
-
通過看題目,我們清楚是要我們求解組合數(shù)的系數(shù)。所以如果我們要求解x^n*y^m的系數(shù),系數(shù)就應該是Ck^n * a^n?* b^m。那么這個Ck^n應該怎么求呢?這么多數(shù)如果我們一個一個硬算的話我們一定很困難和很耗時間的。
-
但是我們學過組合數(shù)的遞推公式就是Cp^j = Cp-1^j-1+Cp-1^j。怎么理解這個公式呢?我們可以想:現(xiàn)在我從一堆蘋果里面隨便挑出了一個蘋果,題目要求我們選擇j個蘋果,那么現(xiàn)在就分為兩種情況一種是包含這個我們挑中的蘋果,那么我們現(xiàn)在只要從p-1個總數(shù)中挑出j-1個蘋果就可以了所以就是Cp-1^j-1;一種是不包含這個蘋果,那么我們要從p-1個蘋果中挑出j個蘋果。只有這兩種情況那么這兩種情況加到一起就可以包括了所有的可能。那么只要遞推過來就可以知道后面的情況了。
? 第二:書寫主函數(shù),構建整體框架:
-
我們把值全部都輸入進去,這里有一個值得注意的地方這個點很細小,就是我們的a,b必須要先求一次模,為什么呢?因為我們的a和b最大都是1e6,如果最后和模相乘一下的話就會是1e10級別的數(shù),那么一定會溢出。所以這里一定要模一下,不然過不去!
-
這里進入兩層for循環(huán)利用好我們的遞推公式,我們判斷一下如果j是0的情況,就相當于從i個蘋果里面選擇0個的方案數(shù),很明顯一個都不選就是一種方案所以方案數(shù)就是1。
-
最終我們得出來的答案就是res[k][n](Ck^n)個方案。
-
我們已經(jīng)把組合數(shù)的系數(shù)值算出來了,接下來就以要計算a和b的次方就行了
int main()
{cin>>a>>b>>k>>n>>m;a %= MOD , b %= MOD;for(int i = 0 ; i <= k ; i ++){for(int j = 0 ; j <= i ; j ++){if(!j) res[i][j] = 1;else res[i][j] = (res[i-1][j-1]+res[i-1][j])%MOD;}}int ans = res[k][n];for(int i = 0 ; i < n ; i ++) ans = ans * a % MOD;for(int i = 0 ; i < m ; i ++) ans = ans *b % MOD;cout<<ans;return 0;
}
代碼:
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1100 , MOD = 10007;int a,b,k,n,m;
int res[N][N] ;int main()
{cin>>a>>b>>k>>n>>m;a %= MOD , b %= MOD;for(int i = 0 ; i <= k ; i ++){for(int j = 0 ; j <= i ; j ++){if(!j) res[i][j] = 1;else res[i][j] = (res[i-1][j-1]+res[i-1][j])%MOD;}}int ans = res[k][n];for(int i = 0 ; i < n ; i ++) ans = ans * a % MOD;for(int i = 0 ; i < m ; i ++) ans = ans *b % MOD;cout<<ans;return 0;
}