当前位置:网站首页>CCPC 2021威海 - G. Shinyruo and KFC(组合数,小技巧)
CCPC 2021威海 - G. Shinyruo and KFC(组合数,小技巧)
2022-07-05 20:08:00 【小酒窝.】
G. Shinyruo and KFC
题意
一共有 n n n 种食物,每种食物有 a i a_i ai 个。食物个数总和不超过 1 0 5 10^5 105。
现在要把这些食物分给 k k k 个人,每个人可以拿多种事物,但每种食物最多拿 1 个。
对于 k k k 从 1 到 m m m,分别输出食物分配方案。
答案模 998244353 998244353 998244353。
1 ≤ m , n ≤ 5 ⋅ 1 0 4 1 \le m,n \le 5 \cdot 10^4 1≤m,n≤5⋅104
0 ≤ a i ≤ 1 0 5 , ∑ i = 1 n a i ≤ 1 0 5 0\le a_i\le 10^5,\ \sum_{i=1}^n a_i\le 10^5 0≤ai≤105, ∑i=1nai≤105
思路
对于一种食物共有 a i a_i ai 个,分给 k k k 个人,每人最多分一个,那么分配方案为 C ( k , a i ) C(k, ai) C(k,ai)。
那么 n 种食物,分给 k 个人总的分配方案为: ∏ i = 1 n C ( k , a i ) \prod_{i=1}^{n} C(k, a_i) ∏i=1nC(k,ai);
再遍历 m 个人,这样的话时间复杂度最低为 O(n * m),超时。
而题目中说 ai 总和不超过 1e5,那么 ai 的种类数就在 1 e 5 \sqrt {1e5} 1e5 级别,对于重复的直接用快速幂求幂次。
预处理逆元求组合数。
这样时间复杂度降为: O ( m n l o g n ) O(m \sqrt n \ logn) O(mn logn)
Code
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long
#define fi first
#define se second
#define endl '\n'
map<int,int> mp;
const int N = 200010, mod = 998244353;
int T, n, m;
int a[N];
struct node{
int x, cnt;
}b[N];
int fac[N], inv[N], finv[N];
int qmi(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1) ans = ans * x % mod;
x = x*x % mod;
y >>= 1;
}
return ans;
}
void init(){
fac[0]=inv[0]=inv[1]=finv[0]=finv[1]=1ll;
for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
for(int i=2;i<N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<N;i++)finv[i]=finv[i-1]*inv[i]%mod;
}
inline int C(int a,int b){
if(b>a)return 0;
else return fac[a]*finv[a-b]%mod*finv[b]%mod;
}
signed main(){
Ios;
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i], mp[a[i]]++;
int cnt = 0;
for(auto it : mp)
{
cnt++;
b[cnt] = {
it.first, it.second};
}
init();
for(int i=1;i<=m;i++)
{
int ans = 1;
for(int j=1;j<=cnt;j++)
{
ans = ans * qmi(C(i, b[j].x), b[j].cnt) % mod;
}
cout << ans << endl;
}
return 0;
}
经验
- 如果 n 个数的总和不超过 m,那么这些数的种类个数在 m \sqrt m m 级别。
边栏推荐
- Bitcoinwin (BCW) was invited to attend Hanoi traders fair 2022
- Tasks in GStreamer
- Force buckle 1200 Minimum absolute difference
- Concept and syntax of function
- 怎么挑选好的外盘平台,安全正规的?
- leetcode刷题:二叉树10(完全二叉树的节点个数)
- leetcode刷题:二叉树11(平衡二叉树)
- Cocos2d-x项目总结中的一些遇到的问题
- No matter how busy you are, you can't forget safety
- -v parameter of GST launch
猜你喜欢
S7-200smart uses V90 Modbus communication control library to control the specific methods and steps of V90 servo
淺淺的談一下ThreadLocalInsecureRandom
Build your own website (16)
JVMRandom不可设置种子|问题追溯|源码追溯
Leetcode skimming: binary tree 16 (path sum)
Fundamentals of deep learning convolutional neural network (CNN)
B站UP搭建世界首个纯红石神经网络、基于深度学习动作识别的色情检测、陈天奇《机器学编译MLC》课程进展、AI前沿论文 | ShowMeAI资讯日报 #07.05
无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
. Net distributed transaction and landing solution
再忙不能忘安全
随机推荐
Add data to excel small and medium-sized cases through poi
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
[C language] merge sort
Four methods of random number generation | random | math | threadlocalrandom | securityrandom
ACM getting started Day1
Oracle-表空间管理
图嵌入Graph embedding学习笔记
Database logic processing function
Common operators and operator priority
leetcode刷题:二叉树11(平衡二叉树)
Based on vs2017 and cmake GUI configuration, zxing and opencv are used in win10 x64 environment, and simple detection of data matrix code is realized
js方法传Long类型id值时会出现精确损失
14. Users, groups, and permissions (14)
Float. The specific meaning of the return value of floattorawintbits is to convert float into byte array
id选择器和类选择器的区别
通配符选择器
Thread pool parameters and reasonable settings
No matter how busy you are, you can't forget safety
Go language learning tutorial (16)
Is it safe for Anxin securities to open an account online?