stdKonjac's Blog

An AC a day keeps the WA away ~

【NOIP2011提高组 计算系数】

题目背景

NOIP2011提高组 DAY2 试题 1 。

题目描述

给定一个多项式(ax + by)k,请求出多项式展开后 xny项的系数。

输入格式

共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。

输出格式

输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取模后的结果。

样例数据 1

输入

1 1 3 1 2

输出

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。

考二项式定理和组合数公式,C(n,m)=C(n,m-1)+C(n-1,m-1)要利用这个性质不然就慢慢写高精度去吧,然后要求的系数就是anbm*C(k,n)(或者C(k,m),因为C(n,m)=C(n,n-m)),之后每乘一次就模一次就行了,话说为啥快速幂会挂掉TAT……必须裸乘。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.