NOIP2011多项式系数
题目描述
求 (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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #define N 1005 #define M 10007 using namespace std; int f[N][N]; int main() { int a,b,k,n,m,i,j,ans; cin>>a>>b>>k>>n>>m; a=a%M;b=b%M; for(i=1;i<=k;i++) {f[i][i]=f[i][0]=1;f[i][1]=i;} for(i=3;i<=k;i++) for(j=2;j<i;j++) f[i][j]=(f[i-1][j]+f[i-1][j-1])%M; ans=f[k][m]%M; for(i=1;i<=n;i++) ans=(ans*a)%M; for(i=1;i<=m;i++) ans=(ans*b)%M; cout<<ans; return 0; } |
2014.4.24
乘法逆元可以用于求C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define P 10007 #define ll long long #define inf (1LL<<60) using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int k,a,b,n,m; int qpow(int x,int y) { int ans=1; x%=P; for(int i=y;i;i>>=1,x=x*x%P) if(i&1)ans=ans*x%P; return ans; } int C(int n,int m) { int s1=1,s2=1; if(m>n-m)m=n-m; for(int i=1;i<=m;i++) { s1=s1*(n-i+1)%P; s2=s2*i%P; } return s1*qpow(s2,P-2)%P; } int main() { a=read();b=read();k=read();n=read();m=read();//C(K,n)*a^n*b^m printf("%d\n",C(k,n)%P*qpow(a,n)%P*qpow(b,m)%P); return 0; } |
逆元用费马小定理+快速幂来求，当然也可以exgcd
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define P 10007 #define ll long long #define inf (1LL<<60) using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int k,a,b,n,m; void exgcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } int qpow(int x,int y) { int ans=1; x%=P; for(int i=y;i;i>>=1,x=x*x%P) if(i&1)ans=ans*x%P; return ans; } int ine(int T)//ax%P=1->ax+Py=1 { int x,y; exgcd(T,P,x,y); x%=P; while(x<=0)x+=P; return x; } int C(int n,int m) { int s1=1,s2=1; if(m>n-m)m=n-m; for(int i=1;i<=m;i++) { s1=s1*(n-i+1)%P; s2=s2*i%P; } return s1*ine(s2)%P;//s1*qpow(s2,P-2)%P; } int main() { a=read();b=read();k=read();n=read();m=read();//C(K,n)*a^n*b^m printf("%d\n",C(k,n)%P*qpow(a,n)%P*qpow(b,m)%P); return 0; } |
计数器 9854675
OI 课件=>
OI 课件=>
#include<iostream>
=((-re 
*a%mod)+mod)%mod;
#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
}
}