2020Nowcode多校 Round5 C. Easy
C. Easy
构造两个序列分别要满足 \(\sum_{i=1}^{k} a_{i} = N\) \(\sum_{i=1}^{k} b_{i} = M\)
一种方案能贡献\(\prod_{i=1}^{k} min(a_{i}, b_{i})\) 的分数 求所有方案分数的和
生成函数
对于一个序列 \(a_{0},a_{1},a_{2}\)···
定义它的生成函数为 \(G(x) = a_{0} + a_{1}x + a_{2}x^{2}\)···
生成函数有指数和系数两维信息 所以用来解决计数问题非常强大 因此生成函数的构造是比较关键的
在本题中一个序列不同的方案数 其实就是就把N划分成K个数的方案数
对于每一个数我们可以用一个生成函数\(G(x) = x+x^{2}+x^{3}\)···来表示
它的意义是 每一项其实就是一种操作 比如\(x^{2}\)表示让这一位为2(指数)的方案数为1(系数)
那么把N划分成K个数的方案数就是 \((G(x))^{k} = (x + x^{2}+x^{3}···)^{k}\) 中\(x^{N}\)的系数
如果想维护出一个序列所有方案分数的和 我们可以巧妙的构造 \((G(x))^{k} = (x + 2x^{2}+3x^{3}···)^{k}\)
它的意义是 比如\(2x^{2}\)表示让这一位为2(指数)能让这一种方案的分数\(*2\)(系数)
min的生成函数
容易想到 对于两个数我们可以构造一个生成函数\(G(x,y) = (x + x^{2} + x^{3}···)(y+y^{2}+y^{3}···)\) 用\(x^{i}y^{j}\)来表示第一个数为i 第二个数为j
我们只用了它的指数 显然还有系数可以用来维护信息 能不能用一种构造使得它的系数为\(min(i,j)\)呢
先上结论 我们可以在\(G(x,y)\)后乘上一个\(1+xy+x^{2}y^{2}\)···
理解一下 假设\(i<j\) 它实际上是提供了一个映射 让原来的\(x^{i}y^{j},x^{i-1}y^{j-1},x^{i-2}y^{j-2}···x^{1}y^{j-i+1}\)一共\(i\)项都为\(x^{i}y^{j}\)的系数做了一次贡献
所以在这个多项式里\(x^{i}y^{j}\)的系数恰好为\(min(i,j)\)
题解
综上所述 答案为\(G(x,y) = (x + x^{2} + x^{3}···)^{k}(y+y^{2}+y^{3}···)^{k}(1+xy+x^{2}y^{2}···)^{k}\)这个多项式中\(x^{N}y^{M}\)的系数
我们可以枚举最后一项中\(x^{i}y^{i}\)的指数 就可以得到第一个项中\(x\)的指数为\(N-i\) 第二项\(y\)的指数为\(M-i\)
然后分别计算它们的系数 最后一项是把i个物品分为K个可以为空的集合 前两项分别是把\(N-i\)和\(M-i\)个物品分为K个非空集合
\(ans = \sum_{0}^{min(N-K,M-K)} \binom{N-i-1}{K-1} \binom{M-i-1}{K-1} \binom{i+K-1}{i}\)
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int MAXN = 1000005;
int n, m, k;
int fac[MAXN];
int ny[MAXN];
int inv[MAXN];
int C(int x, int y) {
if(x < y || y < 0 || x < 0) return 0;
return 1LL * fac[x] * inv[x - y] % mod * inv[y] % mod;
}
int main() {
fac[0] = ny[0] = inv[0] = 1; ny[1] = 1;
for(int i = 1; i <= 1000000; i++) {
fac[i] = 1LL * i * fac[i - 1] % mod;
if(i > 1) ny[i] = 1LL * ny[mod % i] * (mod - mod / i) % mod;
inv[i] = 1LL * ny[i] * inv[i - 1] % mod;
}
int T;
cin>>T;
while(T--) {
scanf("%d%d%d", &n, &m, &k);
int ans = 0;
for(int i = 0; i <= min(n, m) - k; i++) {
int tmp = 1LL * C(k + i - 1, i) * C(n - i - 1, k - 1) % mod * C(m - i - 1, k - 1) % mod;
ans = (ans + tmp) % mod;
}
printf("%d\n", ans);
}
return 0;
}
最新文章
- python文件读写操作与linux shell变量命令交互执行
- 软件工程--界面UI 的原型设计
- servlet获取参数时,request.getParameter(";id";)参数获取失败
- android修改debug keystore文件使之和正式keystore sha1一致
- CLR via C#(16)--泛型
- Eclipse相关设置
- 为 Virtual Box 中的 CentOS 6.6 配置本地DVD光盘做yum软件源
- GDB 使用大法
- IE、chrome、火狐中如何调试javascript脚本
- ElasticSearch 查询语法
- exit和_exit的区别
- Firewalld防火墙
- 对比React Native、dcloud、LuaView三个框架技术(内部)
- html5中的postMessage解决跨域问题
- java 文本图片字体模糊优化处理
- DJango内建模板转向jinja2的小脚本
- 登录获取session
- leetcode 刷题进展
- c# 枚举的定义,枚举的用法,获取枚举值
- spring-cloud-sleuth+zipkin追踪服务实现(一)
热门文章
- idea多模块启动
- web元素定位和appium-app元素定位
- 浅谈localStorage的使用场景和优劣势,以及sessionStorage和cookie
- 【JS学习】String基础方法
- rm: cannot remove `/tmp/localhost-mysql_cacti_stats.txt&#39;: Operation not permitted
- 电子邮箱、邮件地址、网站地址正则表达式!几个有用的RE、regex、regexp!
- XSS - Labs 靶场笔记(下)
- java 不利用第三个变量的情况下将值互换
- Py数据类型—整形与字符串
- Kubernetes之GlusterFS集群文件系统高可用安装,提供动态卷存储