【NOI P模拟赛】(要素过多的标题)(容斥原理)
题面
0 题目背景
[
数
据
删
除
]
_{^{[数\,据\,删\,除]}}
[数据删除]
1 题目描述
在执行任务时,收集到了
n
n
n 份能源,其中第
i
i
i 份的能量值是
w
i
w_i
wi ,她决定将它们分成恰好
k
k
k 组带回基地,每一组都要有至少
1
\tt1
1 份能源。
每一组能源会对运输设备产生负荷值,若该组有
x
x
x 份能源,这
x
x
x 份能源能量值之和为
y
y
y , 则产生的负荷值为
x
×
y
x × y
x×y 。
每种分组方案产生的负荷是每一组能源产生的负荷值总和,想知道所有可能的分组方案产生的负荷之和对
998244353
\tt998244353
998244353 取模的结果。
2 输入格式
输入文件 ichigo.in 包含 2 行。
第 1 行输入两个正整数分别表示
n
,
k
n, k
n,k 。
第 2 行输入
n
n
n 个正整数,其中第
i
i
i 个正整数表示
w
i
w_i
wi 。
3 输出格式
输出文件 ichigo.out 包含一行,仅一个非负整数,表示答案对
998244353
\tt998244353
998244353 取模的结果。
题解
翻译一下,第
i
i
i 份能源的贡献为(所有情况下【
i
i
i 所在的组的大小】之和)×
w
i
w_i
wi 。
然后这个括号里的(所有情况下【
i
i
i 所在的组的大小】之和),对于每个
i
i
i 来说地位是等同的,所以我们求的最终答案就是(所有情况下【一号所在的组的大小】之和)×
∑
w
i
\sum w_i
∑wi 。
我们令( 所有情况下【一号所在的组的大小】之和)为
a
s
as
as 。
首先我们发现,分成
k
k
k 组是无序的,不好办,我们就先让他有序,给每一组一个
1
∼
k
1\sim k
1∼k 的标号,答案除去
k
!
k!
k! 就行了。(这里,不少人会选择【斯特林数】推导,但是这并不方便计算我们的目标)
然后,就可以将
n
n
n 份能源放入
k
k
k 个桶中,统计每份能源与一号能源碰面的概率之和,再乘上总方案数,就能求出 不强制每个桶非空 的答案了:
(
1
k
⋅
(
n
−
1
)
+
1
)
⋅
k
n
(\frac{1}{k}\cdot(n-1)+1)\cdot k^n
(k1⋅(n−1)+1)⋅kn
接下来用容斥,我们令条件
A
i
A_i
Ai 为桶
i
i
i 非空,求所有条件都满足的答案。
可得
a
s
=
∑
i
=
1
k
(
−
1
)
k
−
i
(
(
1
i
(
n
−
1
)
+
1
)
⋅
i
n
)
⋅
(
k
i
)
k
!
as=\frac{\sum_{i=1}^k(-1)^{k-i} \left(\Big(\frac{1}{i}(n-1)+1\Big)\cdot i^n \right)\cdot {k\choose i}}{k!}
as=k!∑i=1k(−1)k−i((i1(n−1)+1)⋅in)⋅(ik)
即最终答案为
(
∑
w
i
)
⋅
∑
i
=
1
k
(
−
1
)
k
−
i
(
(
1
i
(
n
−
1
)
+
1
)
⋅
i
n
)
⋅
(
k
i
)
k
!
(\sum w_i)\cdot\frac{\sum_{i=1}^k(-1)^{k-i} \left(\Big(\frac{1}{i}(n-1)+1\Big)\cdot i^n \right)\cdot {k\choose i}}{k!}
(∑wi)⋅k!∑i=1k(−1)k−i((i1(n−1)+1)⋅in)⋅(ik)
时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn) 。
瓶颈在于求
1
∼
k
1\sim k
1∼k 的
n
n
n 次方用了快速幂,可以用线性筛优化至
O
(
n
)
O(n)
O(n) 。
CODE
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <random>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1000005
#define LL long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
#define FI first
#define SE second
int xchar() {
static const int maxn = 1000000;
static char b[maxn];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(b, 1, maxn, stdin);
if (pos == len)
return -1;
return b[pos++];
}
//#define getchar() xchar()
LL read() {
LL f = 1, x = 0;
int s = getchar();
while (s < '0' || s > '9') {
if (s < 0)
return -1;
if (s == '-')
f = -f;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = x * 10 + (s ^ 48);
s = getchar();
}
return f * x;
}
void putpos(LL x) {
if (!x)
return;
putpos(x / 10);
putchar('0' + (x % 10));
}
void putnum(LL x) {
if (!x) {
putchar('0');
return;
}
if (x < 0) {
putchar('-');
x = -x;
}
return putpos(x);
}
void AIput(LL x, int c) {
putnum(x);
putchar(c);
}
const int MOD = 998244353;
int n, m, s, o, k;
int qkpow(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1)
res = res * 1ll * a % MOD;
a = a * 1ll * a % MOD;
b >>= 1;
}
return res;
}
int fac[MAXN], inv[MAXN], invf[MAXN];
int C(int n, int m) {
if (m < 0 || m > n)
return 0;
return fac[n] * 1ll * invf[n - m] % MOD * invf[m] % MOD;
}
int dp[MAXN];
int main() {
freopen("ichigo.in", "r", stdin);
freopen("ichigo.out", "w", stdout);
n = read();
k = read();
fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * 1ll * i % MOD;
inv[i] = (MOD - inv[MOD % i]) * 1ll * (MOD / i) % MOD;
invf[i] = invf[i - 1] * 1ll * inv[i] % MOD;
}
int ans = 0;
for (int i = 1; i <= n; i++) (ans += read()) %= MOD;
for (int i = 1; i <= k; i++) {
int al = qkpow(i, n);
dp[i] = (inv[i] * 1ll * (n - 1) % MOD + 1) * 1ll * al % MOD;
}
int as = 0;
for (int i = k, l = 1; i > 0; i--, l = MOD - l) {
(as += l * 1ll * dp[i] % MOD * 1ll * C(k, i) % MOD) %= MOD;
}
as = as * 1ll * invf[k] % MOD;
ans = ans * 1ll * as % MOD;
AIput(ans, '\n');
return 0;
}
最新文章
- Divide and conquer:Sumsets(POJ 2549)
- zepto源码--核心方法(类数组相关)--学习笔记
- struts2日常
- MSSQL - 视图操作
- OBIEE SampleAppv406 自己主动启动配置
- 什么是PROFINET IO系统的实时性
- Oracle知识点总结2
- Codeforces Global Round 2
- [C]gcc编译器的一些常用语法
- 【noip模拟赛6】收入计划 最大值的最小值 二分答案
- /etc/apt/sources.list"; E212: Can&#39;t open file for writing解决方案
- 对jQuery ajax的认识
- CentOS 7 安装以及配置
- android读取通讯录和使用系统通讯录
- Parallel Programming-实现并行操作的流水线(生产者、消费者)
- KMP算法(改进后的字符串匹配算法)
- 判断ARP欺骗
- react+node制作在线笔记本(一)
- python中的zipfile
- nginx限制恶意IP处理方法