[Luogu1313][NOIP2011提高组]计算系数

题目描述

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

输入输出格式

输入格式：

共一行，包含

输出格式：

共1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对

输入输出样例

输入样例#1：

1 1 3 1 2

输出样例#1：

说明

【数据范围】

对于 $30%30\%30% 的数据，有 0≤k≤10 0 ≤k ≤100≤k≤10 ；$

对于 $50%50\% 50% 的数据，有 a=1,b=1 a = 1,b = 1a=1,b=1 ；$

对于 $100%100\%100% 的数据，有 0≤k≤1,000,0≤n,m≤k 0≤k ≤1,000,0≤n, m≤k0≤k≤1,000,0≤n,m≤k ,且 n+m=k,0≤a,b≤1,000,000n+m=k ,0 ≤a,b ≤1,000,000n+m=k,0≤a,b≤1,000,000 。$

noip2011提高组day2第1题

题目过水。

二项式定理众所周知。

然后就是裸的逆元了...

ans = $ extrm{C}_{k}^{n} * a^{n}*b^{m}$

取模要彻底。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a, b, n, m, k;
#define ll long long
#define mod 10007
inline ll ksm(ll x, ll y)
{
    ll res = 1;
    while(y)
    {
        if (y&1) res=(ll)(res*x) % mod;
        x = (x * x) %mod;
        y >>= 1;
    }
    return res;
}

ll fac[1000005];

int main()
{
    scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
    fac[1] = 1;
    for (int i = 2 ; i <= k ; i ++) fac[i] = (fac[i-1] * i) % mod;
    ll ans = (((ksm(a, n) * ksm(b, m)) % mod * fac[k]) % mod * (ksm(fac[k-n], mod-2) * ksm(fac[n], mod-2)) % mod) % mod;
    printf("%lld
", ans);
    return 0;
}

$sum_{age=16}^{18} hardworking = success$