NOIP2011多项式系数

2014年4月24日5,8681

题目描述

求 (ax+by)^k 的展开中 x^n*y^m 项的系数。由于系数可能很大,只要求输出除以 10007 的余数。

输入

一行共五个整数,分别为 a,b,k,n,m

输出

一个整数,为该项系数除以10007的余数。

样例输入

1 1 3 1 2

样例输出

3

提示

数据范围:

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

代码

2013.11.6

2014.4.24

乘法逆元可以用于求C

逆元用费马小定理+快速幂来求,当然也可以exgcd

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
zld3794955 Recent comment authors
  Subscribe  
提醒
zld3794955

#include<iostream>
#include<cstdio>
using namespace std;
const int P=10007;
int n=P-1,re[N]={1,1};
int main()
{
for(int i=2;i<=n;++i)
{
int a=P/i,b=P%i;
re =((-re *a%mod)+mod)%mod;
}
}