[NOIp2011] luogu P1313 计算系数

继续水博客，待会回去上术学。

题目描述

给定一个多项式 (by+ax)k(by+ax)^k(by+ax)k ，请求出多项式展开后 xn×ymx^n \times y^mxn×ym 项的系数。

Solution

先看 a=b=1a=b=1a=b=1 的情况，打个表

1

1 1

1 2 1

1 3 3 1

发现是杨辉三角。50分到手。

再看100分。不难发现，答案就是原来的答案乘 an×bma^n\times b^man×bm，于是这道题就做完了，甚至连快速幂都不用。

#include<cstdio>

#include<cstdlib>

#include<cstring>

const int MAXN=1010;

const int MOD=10007;

int f[MAXN][MAXN];

int a,b,k,n,m;

void init(){

	for(int i=1;i<=k+1;++i){

		f[i][1]=f[i][i]=1;

		for(int j=2;j<i;++j)

			f[i][j]=(f[i-1][j]+f[i-1][j-1])%MOD;

	}

}

int pow(int x,int y){

	if(y==1) return x;

	int c=pow(x,y/2);

	if(y%2)

		return c*c%MOD*x%MOD;

	return c*c%MOD;

}

int main(){

	scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);

	init();

	printf("%d",f[k+1][k-n+1]*pow(a%MOD,n)%MOD*pow(b%MOD,m)%MOD);

}

巴特西

[NOIp2011] luogu P1313 计算系数

题目描述

Solution

最新文章

热门文章