1746: 多項式系數
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 369 Solved: 79
[Submit][Status][Web Board]
Description

求 (ax+by)^k 的展開中 x^n*ym 項的系數。由于系數可能很大，只要求輸出除以 10007 的余數。

Input

一行共五個整數，分別為 a,b,k,n,m

Output

一個整數，為該項系數除以10007的余數。

Sample Input

1 1 3 1 2

Sample Output

3

HINT

數據范圍：

30% 0<=k<=10,

50% a=1,b=1

100% 0<=k<=1000, 0<=n,m<=k 且 n+m=k, 0<=a,b<=100,000

NOIP2011 DAY2 factor

Source

NOIP2011
//很久之前做的
AC_code~:

#include<stdio.h>#define r 10007int c[1001][1001]= {0};int Can(int a,int n){a = a % r;//a也可能比較大，需要預先對a處理int z = a;for(int i = 1; i < n; i++) //求a的n次方，由于數據還可能比較大，要求余，那就邊乘邊余，(b,m)也適用a = z * a % r;return a;}int main(){int a,b,k,n,m,p,q;scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);//楊輝三角，數據可能比較大，要求余，so都邊求值邊取余c[0][0]=1;for(int i = 1; i <= k; i++){c[i][0]=1;//第一列都為1for(int j = 1; j <= i; j++)c[i][j] = (c[i-1][j] + c[i-1][j-1]) % r;}p=(Can(a,n))*(Can(b,m))%r;q=c[k][n] * p % r;printf("%d\n",q);return 0;}

總結

以上是生活随笔為你收集整理的1746: 多项式系数（杨辉三角的应用）的全部內容，希望文章能夠幫你解決所遇到的問題。

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