[NOIP2011提高组day2]-1-计算系数

1．计算系数
(factor.cpp/c/pas)
【问题描述】
k n m
给定一个多项式(ax+by)^k ，请求出多项式展开后(x^n)*(y^m)项的系数。
【输入】
输入文件名为 factor.in。
共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。
【输出】
输出文件名为 factor.out。
输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取
模后的结果。

【输入输出样例】
factor.in
1 1 3 1 2
factor.out
3

【数据范围】
对于 30%的数据，有 0≤k≤10；
对于 50%的数据，有 a = 1，b = 1；
对于 100%的数据，有 0≤k≤1,000，0≤n, m≤k，且 n + m = k，0≤a，b≤1,000,000。

二项式系数：

是解决这道题的最直接方法；

很容易得出ans=a^n*b^m*c(k,m)

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<iomanip>

#include<map>

#include<set>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

using namespace std;

#define LL long long

#define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)

#define max(x,y) ((x)<(y)?(y):(x))

#define min(x,y) ((x)<(y)?(x):(y))

#define FILE "1"

const int maxn=,mod=;

int a,b,k,n,m;

int c[maxn][maxn];

namespace OI{

    void init(){scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);}

    int getc(int d){

        if(d>k-d)d=k-d;

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

            c[i][]=;

            for(int j=;j<=d&&j<=i;j++){

                if(!c[i][i-j])c[i][j]=(c[i-][j]+c[i-][j-])%mod;

                else c[i][j]=c[i][i-j];

            }

        }

        return c[k][d];

    }

    void slove(){

        init();

        a%=mod,b%=mod;

        LL ans=;

        up(i,,n)ans=ans*a%mod;

        up(i,,m)ans=ans*b%mod;

        ans=ans*getc(m)%mod;

        cout<<ans<<endl;

    }

}

int main(){

    using namespace OI;

    slove();

}

巴特西

[NOIP2011提高组day2]-1-计算系数

最新文章

热门文章