闲话
我发现我浏览器抽风所以我随时保存
上面那个是我改标题为[闲话+日期]前的暂标题/占位符
以前的暂标题就很暂（
有好奇的读者可以猜一猜
就是 今天看到了……忘记了 但是点进了 ARC106D
然后就浅做了一下
又是荒废(?)网络流的一天呢（
推流jjdw的鲜花
感觉这两天下载上传资料电脑卡顿程度直线上升
《感觉是该清灰了》
《其实我的浏览器经常有黑屏啦倒是 我也不知道为什么》
《点开我的浏览器的时候有一定的概率》
《得按照一定的顺序 : (》
《这不是挺好的嘛》
妈妈生的（即答
杂题
给定长度为 \(n\) 的序列 \(a\)，以及一个整数 \(k\)。
对于每个 \(1\le x \le k\)，求出如下式子的值：
\[\sum_{l=1}^{n-1}\sum_{r=l+1}^n \left(a_l + a_r\right)^ x \]答案对 \(998244353\) 取模。
\(2\le n \le 2\times 10^5,\ 1 \le k \le 300, \ 1\le a_i \le 10^8\)。
不难发现，
\[\sum_{l=1}^{n}\sum_{r=1}^n \left(a_l + a_r\right)^x = 2\sum_{l=1}^{n-1}\sum_{r=l+1}^n \left(a_l + a_r\right)^x +\sum_{l=1}^{n}\left(a_l + a_l\right)^x \]于是可以计算
\[\sum_{l=1}^{n}\sum_{r=1}^n \left(a_l + a_r\right)^x \]减去
\[\sum_{l=1}^{n}\left(a_l + a_l\right)^x \]后除二就是答案。
根据二项式定理，可以得到
\[\begin{aligned} &\sum_{l=1}^{n}\sum_{r=1}^n \left(a_l + a_r\right)^x \\ = \ & \sum_{l=1}^{n}\sum_{r=1}^n\sum_{i=1}^x \binom{x}{i} a_l^i a_r^{x-i} \\ = \ & \sum_{i=1}^x \sum_{l=1}^{n}\sum_{r=1}^n\frac{a_l^i}{i!} x!\frac{a_r^{x-i}}{(x - i)!} \\ = \ & \sum_{i=1}^x x!\left(\sum_{l=1}^{n}\frac{a_l^i}{i!}\right) \left(\sum_{r=1}^n\frac{a_r^{x-i}}{(x - i)!}\right) \end{aligned}\]由于 \(x\) 的范围小，可以支持 \(O(k^2)\) 的复杂度，我们可以枚举 \(x\) 和 \(i\) 合并答案。
对每个 \(1\le m\le k\) 预处理
\[\sum_{l=1}^{n}\frac{a_l^m}{m!} \]即可做到 \(O(k^2)\) 合并答案。合并答案也可应用卷积，但复杂度瓶颈不在这里。
朴素合并的总时间复杂度为 \(O(nk + k^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
template <typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
const int N = 4e5 + 10;
int n, k, sum[305], a[N], v[305];
signed main() {
get(n, k); rep(i,1,n) get(a[i]);
init_fac(305);
v[0] = n;
rep(j,1,n) {
int t1 = 1, t2 = 1;
rep(i,1,k) {
t1 = mul(t1, a[j]), t2 = mul(t2, 2 * a[j]);
v[i] = add(v[i], mul(t1, ifc[i]));
sum[i] = add(sum[i], t2);
}
}
rep(x,1,k) {
int ans = 0;
rep(i,0,x) ans = add(ans, mul(v[i], v[x - i]));
ans = mul(ans, fac[x]);
ans = sub(ans, sum[x]);
cout << mul(ans, inv2) << '\n';
}
}
你有 \(n\) 个朋友，他们会来你家玩，第 \(i\) 个人 \(1\sim A_i\) 天来玩，然后 \(A_i+1\sim 2A_i\) 天不来，然后 \(2A_i+1\sim 3A_i\) 天又会来，以此类推。
每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。你要给每个人都颁 \(K\) 个奖，问至少需要多少天。
\(1\le n\le 18, \ 1\le k \le 10^5, \ 1\le A_i \le 10^5\)。
二分答案转化为判定。
判定的话考虑建二分图。假设当前的天数是 \(t\)，左部点是 \(t\) 天，右部点是 \(n \times k\) 个人对应的奖。每个人和他会来玩的那些天连边，流就是奖。最后看是不是能流满即可。
我们发现，这就是在寻找二分图完全匹配。由于人数少，考虑把一天来的人压成状态。施 Hall 定理，我们只需要考虑每个状态 \(i\) 能和多少天连边，也就是有多少天对应的状态和它有交。假设这个值是 \(s\)，则该状态满足要求当且仅当 \(s \ge \text{popcount}(i) \times k\)。所有状态满足要求则 \(t\) 满足要求。
考虑求有多少天的状态是状态 \(i\) 的补集的子集，再用 \(t\) 减去就是状态 \(i\) 的 \(s\)。应用 SOS DP 可以得到答案。
二分边界？容易发现 \(2nk\) 一定满足要求。
总时间复杂度 \(O(n2^n\log (nk))\)。
code
#include <bits/stdc++.h>
using namespace std; using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> T rand(T l, T r) { return uniform_int_distribution<T>(l, r)(rnd); }
template <typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
template <typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
template <typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define ufile(x)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define Aster(i, s) for (int i = head[s], v; i; i = e[i].next)
#define all(s) s.begin(), s.end()
#define pcnt(x) __builtin_popcount(x)
#define eb emplace_back
#define pb pop_back
#define em emplace
const int N = 1e7 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, k, m, a[N], f[N];
int g[N];
bool check(int d) {
rep(i,0,(1<<n)-1) g[i] = 0;
rep(i,1,d) g[f[i]] ++;
rep(i,0,n-1) rep(j,0,(1<<n)-1) {
if (!(j >> i & 1))
g[j | (1 << i)] += g[j];
}
rep(i,0,(1<<n)-1) if (d - g[(1 << n) - 1 - i] < pcnt(i) * k) return false;
return true;
}
signed main() {
get(n, k); rep(i,1,n) get(a[i]);
m = 2 * n * k;
rep(i,1,m) rep(j,1,n) if (((i + a[j] - 1) / a[j]) & 1) f[i] |= 1 << j - 1;
int l = 1, r = m, mid;
while (l <= r) {
mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << r + 1 << '\n';
}
有 \(n\) 个点，每个点有 \(a_i\) 个孔，每次可以选择两个不同点，连接两个未被连接过的孔，有多少中方案使得最后形成一棵树。
答案对 \(998244353\) 取模。\(2\le n \le 2\times 10^5, \ 1\le d_i \le 998244352\)。
\(\text{Solution 1}\) 生成法计数
官方题解采用的方法。
首先可以发现只有当 \(\sum d_i \ge 2(n - 1)\) 时有解。
随后考虑如何生成所有可能的方案。我们称一个联通的子图为一个分量，最开始有 \(n\) 个分量。
最开始在每个分量上选取一个特殊点。随后按如下方式操作：
- 将分量数量减小到 \(2\)。
- 选择一个非特殊点 \(a\)。
- 选择一个不与点 \(a\) 位于同一分量中的特殊点 \(b\)。
- 连接 \(a,b\)。新分量的特殊点是其中一个距离 \(a,b\) 最近的可连边的点。
- 连接最后的两个分量上的特殊点。
最开始选择特殊点的方案数是 \(\prod_{i=1}^n d_i\)。记 \(S = \sum_{i=1}^n d_i\)，第 \(i\) 次选择时非特殊点数量为 \((S - n - (i-1))\) 个，能连接的联通块数是 \((n - i)\) 个，自然导出了方案数
\[\prod_{i=1}^n d_i\times \prod_{i=1}^{n-2} (n - i) (S - n - (i - 1)) = \prod_{i=1}^n d_i\times (n - 1)!\times \prod_{i=0}^{n-3} (S - n - i) \]考虑生成方式，我们发现同一棵树会以不同的加边顺序在答案中被统计 \((n-1)!\) 次，因此最终答案为
\[\prod_{i=1}^n d_i\times \prod_{i=0}^{n-3} (S - n - i) \]\(\text{Solution 2}\) 生成函数
首先固定每个点 \(i\) 在最终生成的树中的度数 \(r_i\)。
由 prufer 序列导出结论，一棵满足上述度数条件的树的计数是
\[\frac{(n - 2)!}{ \prod_{i=1}^n (r_i - 1)! } \]证明考虑计数 prufer 序列，元素 \(i\) 在其中出现了 \(r_i - 1\) 次。
每个点在连接时是有序的，因此在度数固定为 \(r\) 的情况下，贡献是
\[\frac{(n - 2)!}{ \prod_{i=1}^n (r_i - 1)! }\times \prod_{i=1}^n A_{d_i}^{r_i} \]可以发现 \(\sum r_i = 2(n - 1)\)。因此不妨从卷积的角度入手，枚举 \(r_i\) 的取值。
发现 \((n - 2)!\) 是所有可能都会贡献的，因此只需要生成剩余部分即可。
设 \(F_i(x)\) 为点 \(i\) 对答案的贡献的生成函数，有
\[\begin{aligned} F_i(x) &= \sum_{k=0}^{\infty} \frac{A_{d_i}^k}{(k - 1)!}x^k \\ & = \sum_{k=0}^{\infty} \binom{d_i} k k \ x^k \\ & = d_i \sum_{k=1}^{\infty} \binom{d_i - 1} {k - 1}\ x^k \\ & = d_i x \sum_{k=0}^{\infty} \binom{d_i - 1} {k} \ x^k \\ & = d_i x (1 + x)^{d_i - 1} \end{aligned}\]可以写出答案
\[\begin{aligned} & (n - 2)!\times [x^{2(n-1)}] \prod_{i=1}^nF_i(x) \\ = \ & (n - 2)!\times [x^{2(n-1)}] \prod_{i=1}^n d_i x (1 + x)^{d_i - 1} \\ = \ & (n - 2)!\times\prod_{i=1}^n d_i \times [x^{n - 2}] \prod_{i=1}^n (1 + x)^{d_i - 1} \end{aligned}\]记 \(S = \sum_{i=1}^n d_i\)，有
\[\begin{aligned} & (n - 2)!\times\prod_{i=1}^n d_i \times [x^{n - 2}] \prod_{i=1}^n (1 + x)^{d_i - 1} \\ = \ & (n - 2)!\times\prod_{i=1}^n d_i \times [x^{n - 2}] (1 + x)^{S - n} \\ = \ & (n - 2)!\times\prod_{i=1}^n d_i \times \binom{S - n}{n-2} \\ = \ & \prod_{i=1}^n d_i \times (S - n)^{\underline{n - 2}} \\ = \ & \prod_{i=1}^n d_i\times \prod_{i=0}^{n-3} (S - n - i) \end{aligned}\]两种做法得到了相同的答案。
总时间复杂度为 \(O(n)\)。
个人认为 \(\text{Solution 2}\) 更简单易懂一些。
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
const int mod = 998244353;
int n, prod = 1, sum, tmp;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
rep(i,1,n) {
cin >> tmp;
prod = 1ll * prod * tmp % mod, sum += tmp;
if (sum >= mod) sum -= mod;
}
rep(i,0,n-3) prod = 1ll * prod * (sum - n - i) % mod;
cout << prod << '\n';
}