luogu1313 计算系数
2024-08-27 02:05:58
题目大意:给定一个多项式(ax+by)^k,请求出多项式展开后x^n*y^m 项的系数。
将原式化为(ax+by)*(ax+by)*...①,然后将其拆解,拆解时x乘了多少次,a就乘了多少次,y,b同理。故设所求为t*a^n*b^m。因为拆解时相当于在①括号各个括号内提取出n个x,在剩余的括号内提取出y,不同的组合方式对应一个展开后的项a^n*b^m*x^n*y^(k-M),所以t等于C(k, a)。
怎么求组合数呢?利用C(r, r)=1, C(n, 0)=1, C(n, r)=C(n-1,r-1)+C(n-1,r)(n>r)进行递推即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define ll long long
const ll P = 10007, MAX_K = 1010; ll Mult(ll a, ll b)
{
ll ans = 0;
while (b)
{
if (b & 1)
ans = (ans + a) % P;
a = (a + a) % P;
b >>= 1;
}
return ans;
} ll Power(ll a, ll n)
{
ll ans = 1;
while (n)
{
if (n & 1)
ans = Mult(ans, a);
a = Mult(a, a);
n >>= 1;
}
return ans;
} int Comb(int r, int n)
{
static ll C[MAX_K];
memset(C, 0, sizeof(C));
C[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = min(r, i); j >= 0; j--)
{
if (i == j)
C[j] = 1;
else
C[j] = (C[j - 1] + C[j]) % P;
}
}
return C[r];
} int main()
{
ll a, b, k, n, m;
scanf("%lld%lld%lld%lld%lld", &a, &b, &k, &n, &m);
printf("%lld\n", Mult(Comb(n, k), Mult(Power(a, n), Power(b, m))));
return 0;
}
最新文章
- 【CSS进阶】CSS 颜色体系详解
- HTML中块级元素与行内元素
- Spring-Boot - 初步搭建
- uiscrollView UINavigation和uitabbar添加约束的问题
- Bootstrap<;基础一>; CSS 概览
- 通讯录(ios自带无界面)
- centos 端口开放及关闭
- debian下安装AMD驱动
- oc文件基本读写及操作
- Android--------- SD卡存储文件报错解决
- node.js如何制作命令行工具(一)
- PHP 上传文件大小限制
- Kotlin + Spring Boot 请求参数验证
- ASP.NET Core 快速入门【第二弹-实战篇】
- Netty——简单创建服务器、客户端通讯
- Oracle 参数文件spfile
- git从安装到使用
- 添加全局函数$.extend和对象方法$.fn
- linux下常用的日志分析命令
- 共享设置及ftp设置