https://www.luogu.org/problemnew/show/P1313
題目描述
給定一個多項式(by+ax)^k
，請求出多項式展開后x^ny^m 項的系數。

輸入輸出格式
輸入格式：
共一行，包含55個整數，分別為a ,b ,k ,n ,m，每兩個整數之間用一個空格隔開。

輸出格式：
共1 行，包含一個整數，表示所求的系數，這個系數可能很大，輸出對10007取模后的結果
輸入輸出樣例
輸入樣例#1：

1 1 3 1 2

輸出樣例#1：

3

說明
【數據范圍】

對于30%30% 的數據，有 0 ≤k ≤10；

對于50% 50%的數據，有 a = 1,b = 1；

對于100%的數據，有 0≤k ≤1,000,0≤n, m≤k且n+m=k ,0 ≤a,b ≤1,000,000,n+m=k,0≤a,b≤1,000,000。

noip2011提高組day2第1題
/*
這題在很久之前做過，現在再做了一遍
數學忘的差不多了，所以就重新推了一遍公式：
（ax + by）^ k
要拼湊出（x ^ n y^m）
首先一定有：n + m = k（現在我才發現題目后面有提到。。）
只有k個（ax + by）中選n個是ax,k-n = m個只能選by
所以根據組合得到：

ans= C(k,n) * a^n * b^m

a^n * b^m 這部分好辦，直接來個快速冪（當然不用也是可以，效率低一點），但是都需要注意一個問題，用a之前要先a %= mod,或者數據類型用long long ,因為 a = a * a % mod 中的a * a 會超過int
但是對于C(k,n)，沒有除法取模的相關公式，直接算是覺對不行的，我之前做過，所以直接想到了楊輝三角可以算出C(k,n)，自己展開（x + y）^2, (x + y)^3也可以發現他們系數分別是：
1 2 1，
1 3 3 1
對于x^n y^m,a = 1,b= 1的系數是楊輝三角中的c[k][n] + c[k][m]
但是a,b系數不一定都為1，最終得到: ans = a ^ n * b ^ m*(c[k][n] + c[k][m])
也有：c[k][n] + c[k][m] = c[k+1][n+1] (這里下標都從1開始，我為了楊輝三角打表少打一行，沒有用這個）
這個可以參考之前我的做法：傳送門
*/

#include <iostream>using namespace std; typedef long long LL; const LL mod = 1e4 + 7; //除了數組內存要考慮一下，int最好用long long，不容易錯 int c[1005][1005]; LL quickPow(LL a,LL b) {//a %= mod;LL res = 1;while(b){if(b&1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res % mod; } int main() {LL a,b,k,n,m;cin>>a>>b>>k>>n>>m;for(int i = 1; i <= k; i++){c[i][1] = 1;c[i][i] = 1;}for(int i = 2; i <= k; i++){for(int j = 2; j <= k; j++){c[i][j] = (c[i-1][j]%mod + c[i-1][j-1]%mod)%mod;}}//cout<<c[k][n]<<" "<<c[k][m]<<endl;LL ans = (c[k][n] + c[k][m]) % mod;// cout<<ans<<endl;LL temp = (quickPow(a,n)%mod * quickPow(b,m)%mod)%mod;ans = (ans%mod * temp%mod)%mod;cout<<ans<<endl;return 0; }

總結一下：
求排列組合中的組合數C（k,n）當無法直接求解時，要想到用楊輝三角來計算~~

總結

以上是生活随笔為你收集整理的P1313 计算系数（组合数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。