[NOIP2011]计算系数

发布于 2017-08-19  24 次阅读



题目(vijos)
首先观察数据范围......嗯,k<=1000,杨辉三角可以打表打出来。
用个dp[i][j]表示第i行第j个数的系数(即用dp数组来存这个三角形)。
然后就很简单了,取M=min(n,m),
答案为(a^n*b^m*dp[k+1][M] 还要用快速幂来计算a^n,b^m。
不过也可以不用快速幂。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const ll mod=10007;
int a,b,k,n,m;
ll dp[1005][1005];
ll mi(ll a,ll b)
{
	ll ans=1;
	while (b)
	{
		if (b&1) ans=((an
		a=((
		b>>=1;
	}
	return ans;
}
void ditui()
{
	for (register int i=1;i<=1001;++i)
	{
		for (register int j=0;j<i;++j)
		{
			if (j==0) dp[i][j]=1;
			else
			{
				dp[i][j]=((dp[i-1][j
			}
		}
	}
}
int main()
{
	scanf(
	ditui();
	if (k==0)
	{
		printf("1");
		return 0;
	}
	if (k>1) k++;
	ll a1=mi(a,n);
	ll b1=mi(b,m);
	ll ans;
	if (m<n)
	{
		ans=(a1*b1*dp[k][m]
	}
	else
	{
		ans=(a1*b1*dp[k][n]
	}
	printf(
	return 0;
}