当前位置:网站首页>CCPC 2021 Weihai - G. shinyruo and KFC (combination number, tips)
CCPC 2021 Weihai - G. shinyruo and KFC (combination number, tips)
2022-07-05 20:23:00 【Dimple】
G. Shinyruo and KFC
The question
Altogether n n n Kind of food , Each food has a i a_i ai individual . The total number of food should not exceed 1 0 5 10^5 105.
Now I want to share these foods with k k k personal , Everyone can take many things , But each kind of food takes at most 1 individual .
about k k k from 1 To m m m, Output the food distribution plan separately .
Answer model 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
Ideas
Common to one food a i a_i ai individual , among k k k personal , Each person can get one at most , Then the distribution scheme is C ( k , a i ) C(k, ai) C(k,ai).
that n Kind of food , among k The overall personal distribution plan is : ∏ i = 1 n C ( k , a i ) \prod_{i=1}^{n} C(k, a_i) ∏i=1nC(k,ai);
Re traversal m personal , In this case, the minimum time complexity is O(n * m), Overtime .
And the title says ai The total does not exceed 1e5, that ai The number of species is 1 e 5 \sqrt {1e5} 1e5 Level , For repetition, use fast power to find power .
Preprocess the inverse element to find the combination number .
In this way, the time complexity is reduced to : 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;
}
Experience
- If n The sum of the numbers does not exceed m, Then the number of types of these numbers is m \sqrt m m Level .
边栏推荐
- B站UP搭建世界首个纯红石神经网络、基于深度学习动作识别的色情检测、陈天奇《机器学编译MLC》课程进展、AI前沿论文 | ShowMeAI资讯日报 #07.05
- Informatics Olympiad 1338: [example 3-3] hospital setting | Luogu p1364 hospital setting
- 【c语言】快速排序的三种实现以及优化细节
- 插值查找的简单理解
- 【数字IC验证快速入门】7、验证岗位中必备的数字电路基础知识(含常见面试题)
- leetcode刷题:二叉树10(完全二叉树的节点个数)
- 炒股开户最低佣金,低佣金开户去哪里手机上开户安全吗
- USACO3.4 “破锣摇滚”乐队 Raucous Rockers - DP
- Summer Challenge harmonyos - realize message notification function
- Ros2 topic [01]: installing ros2 on win10
猜你喜欢
How to select the Block Editor? Impression notes verse, notation, flowus
Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage
【数字IC验证快速入门】7、验证岗位中必备的数字电路基础知识(含常见面试题)
Leetcode (695) - the largest area of an island
【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
【愚公系列】2022年7月 Go教学课程 004-Go代码注释
Elk distributed log analysis system deployment (Huawei cloud)
鸿蒙os第四次学习
小程序全局配置
Leetcode(695)——岛屿的最大面积
随机推荐
插值查找的简单理解
[C language] three implementations of quick sorting and optimization details
leetcode刷题:二叉树10(完全二叉树的节点个数)
1:引文;
sun.misc.BASE64Encoder报错解决方法[通俗易懂]
强化学习-学习笔记4 | Actor-Critic
Is it safe for Galaxy Securities to open an account online?
Hong Kong stocks will welcome the "best ten yuan store". Can famous creative products break through through the IPO?
Leetcode brush questions: binary tree 18 (largest binary tree)
Leetcode (695) - the largest area of an island
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
【c语言】快速排序的三种实现以及优化细节
IC科普文:ECO的那些事儿
[quick start of Digital IC Verification] 7. Basic knowledge of digital circuits necessary for verification positions (including common interview questions)
Cocos2d-x项目总结中的一些遇到的问题
1. Strengthen learning basic knowledge points
Rainbond 5.7.1 支持对接多家公有云和集群异常报警
银河证券在网上开户安全吗?
Go language | 01 wsl+vscode environment construction pit avoidance Guide
基础篇——配置文件解析