闲话
今日闲话【碎片】(2/3)
几天前在家看 gdkoi 啥都不会
现在在学校看 gdkoi 仍然啥都不会
；；
改完题到七点了（
今天杂题等等再写（
jdw 怎么那么喜欢翻人旧闲话啊 马上写马上写（
今日推歌：Virtual to LIVE
模拟赛
GDKOI2023 day1。感谢广东同袍不远万里送来的神秘题（
《传统计数强省的一点 998244353 震撼》
T1
签到题。我们要满足 \(AB = C\)，不妨随一个向量 \(\bm b\) 左乘两侧，也就是 \(\bm b AB = C\)。这可以做三次 \(O(n^2)\) 的乘法得到两侧。直接判结果向量是否相同即可，可以知道错误率极小。
不放心可以多随几次。时间复杂度 \(O(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
const int N = 3e3 + 10, mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, a[N][N], b[N][N], c[N][N], vect[N], vect2[N], vect3[N], vect4[N];
mt19937 rnd(random_device{}());
int rint(int l, int r) { return uniform_int_distribution<int>(l, r)(rnd); }
signed main() {
multi {
cin >> n;
rep(i,1,n) rep(j,1,n) cin >> a[i][j];
rep(i,1,n) rep(j,1,n) cin >> b[i][j];
rep(i,1,n) rep(j,1,n) cin >> c[i][j];
bool OK = true;
rep(i,1,3) {
rep(j,1,n) vect[j] = rint(1, 998244353), vect2[j] = vect3[j] = vect4[j] = 0;
rep(j,1,n) rep(k,1,n) vect2[j] = (vect2[j] + 1ll * vect[k] * b[j][k]) % mod;
rep(j,1,n) rep(k,1,n) vect3[j] = (vect3[j] + 1ll * vect2[k] * a[j][k]) % mod;
rep(j,1,n) rep(k,1,n) vect4[j] = (vect4[j] + 1ll * vect[k] * c[j][k]) % mod;
rep(j,1,n) if (vect4[j] != vect3[j]) { OK = false; break; }
if (!OK) break;
} cout << (OK ? "Yes" : "No") << '\n';
}
}
T2
场外看到题时一眼莫队维护转移，但是想了一阵子没思路。
首先 \(2 m > n\) 时无解，判掉。
我们在 \(n - m\) 个数里选 \(m\) 个数放在前 \(i\) 个位置上，方案数是 \(A_{n - m}^m\) 的。剩下了 \(m\) 个 \(1 \sim m\) 的数，以及 \(n - 2m\) 个 \(m+1 \sim n\) 的数，我们要把他们错位地放在 \(m+1 \sim n\) 上。
重新设变量，我们要在 a + b 个位置上放 a + b 个数，其中 a 个数有唯一限制，b 个数不限制。考虑容斥，对确定的 \(a, b\)，\(f(k)\) 是有恰好 \(k \le a\) 个数的限制不满足的方案数，\(g(k)\) 是有至少 \(k\) 个数的限制不满足的方案数。可以知道
可以知道 \(g(k) = \dbinom{a}{k} (a + b - k)!\)，也就是
\[f(a, b) = f(0) = \sum_{i = 0}^a (-1)^{i} \binom{a}{i} (a + b - i)! \]我们可以在 \(O(n)\) 的复杂度内求出单个 \(f(a, b)\)。对 \(n, m\)，答案就是 \(A_{n - m}^m\times f(n - 2m, m)\)。常数优秀的可能可以过 60pts。
可以预料到最后 \(f\) 存在递推形式，我们考虑用莫队优化求解。打表可以发现
然后考虑构造莫队。
我们存下 \(f(n, m)\) 和 \(f(n + 1, m)\)，这样第一维 \(+1\) 可以看出是
减一是同构的。
考虑第二维，我们应用上面的递推式可以知道
以及
\[f(n + 1, m + 1) = (m + 1) f(n + 1, m) + (n + 1) f(n, m + 1) \]减一是同构的。
视 \(m, T = O(n)\)，有总时间复杂度 \(O(n\sqrt n)\)。
听说存在使用 ODE 科技的 \(\log\) 做法。哪位可以教教我？
code
#include <bits/stdc++.h>
using namespace std;
#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)
const int N = 2e5 + 10, mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int q, t1, t2, fac[N], inv[N], ifc[N], ans[N], B = 450;
struct query {
int n, m, bel, id;
bool operator < (const query &b) const {
if (bel != b.bel) return bel < b.bel;
return (bel & 1) ? m < b.m : m > b.m;
}
} qu[N];
int C(int n, int m) { if (n < 0 or n < m or m < 0) return 0; return 1ll * fac[n] * ifc[m] % mod * ifc[n - m] % mod; }
inline void addn(int &n, int &m, int &fnm, int &fn1m) {
int fn2m = (1ll * (n + 1) * fnm + 1ll * (n + m + 1) * fn1m) % mod;
fnm = fn1m, fn1m = fn2m; ++ n;
}
inline void subn(int &n, int &m, int &fnm, int &fn1m) {
int fn_1m = (fn1m - 1ll * (n + m) * fnm % mod + mod) * inv[n] % mod;
fn1m = fnm, fnm = fn_1m; -- n;
}
inline void addm(int &n, int &m, int &fnm, int &fn1m) {
fnm = (fnm + fn1m) % mod;
fn1m = (1ll * (m + 1) * fn1m + 1ll * (n + 1) * fnm) % mod;
++ m;
}
inline void subm(int &n, int &m, int &fnm, int &fn1m) {
fn1m = (fn1m - 1ll * (n + 1) * fnm % mod + mod) % mod * inv[m] % mod;
fnm = (fnm - fn1m + mod) % mod;
-- m;
}
signed main() {
fac[0] = fac[1] = ifc[0] = ifc[1] = 1, inv[1] = 1;
rep(i,2,2e5) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
rep(i,2,2e5) ifc[i] = 1ll * ifc[i - 1] * inv[i] % mod;
cin >> q;
rep(i,1,q) cin >> t1 >> t2, qu[i] = { t1 - 2 * t2, t2, t1 / B, i };
sort(qu + 1, qu + 1 + q);
for (int i = 1, n = 0, m = 0, fnm = 1, fn1m = 0; i <= q; ++ i) {
if (qu[i].n >= 0) {
while (m < qu[i].m) addm(n, m, fnm, fn1m);
while (n < qu[i].n) addn(n, m, fnm, fn1m);
while (m > qu[i].m) subm(n, m, fnm, fn1m);
while (n > qu[i].n) subn(n, m, fnm, fn1m);
ans[qu[i].id] = 1ll * fac[n + m] * ifc[n] % mod * fnm % mod;
} else ans[qu[i].id] = 0;
}
rep(i,1,q) cout << ans[i] << '\n';
}
T3
记值域是 \(V\)，全集是 \(U\)。
首先考虑 \(m = 0\) 的情况。假设存在 \(i\) 满足存在一位使得 \(a_i\) 这位是 \(1\) 且 \(b_i\) 这一位是 \(0\)，则 \(b_i\) 以后的位都可以任意选择，这样其他的数无论是什么值都存在恰好一种合法方案，可以快速算出。因此我们只需要考虑所有 \(b_i\) 在这一位都和 \(a_i\) 相同的情况，递归向下即可。这样可以 \(O(n\log V)\) 计算。
这启发我们采用容斥计算答案。我们枚举一个边集，考虑这些边使得 \(b_u = b_v\)，其他边随意。这会形成许多 \(b\) 彼此相同的连通块，这 \(b\) 小于连通块内最小的 \(a\)，称这个 \(a\) 为对应的连通块的代表值。如果连通块大小是偶数可以忽略，反之把代表值加入一个集合，对这个集合做上面的做法即可。复杂度 \(O(2^m n\log V)\)。
考虑不枚举边集，而是枚举点集，并计算它对答案的容斥系数。考虑一个边集 \(S\) 使得连通块连通，我们知道这时需要钦定 \(S\) 内每条边都使得 \(b_u = b_v\)，因此 \(S\) 对答案的容斥系数是 \((-1)^{|S|}\)。因此这连通块对答案的贡献是 \(\sum_S (-1)^{|S|}\)。求容斥系数可以删点并枚举子集得到。这部分的复杂度是 \(O(3^n)\)。
然后考虑设 \(f(A, S)\) 表示当前连通块组成的点集是 \(A\)，大小为奇数的连通块的代表值组成的下标集合是 \(S\) 的情况下，容斥系数的和。我们需要的就是每个 \(f(U, S)\)，随后对 \(S\) 对应的集合做 \(m = 0\) 的做法即可。转移考虑枚举连通块 \(T\)，由于 \(S\subseteq A\)，我们只需要让 \(T\subseteq \complement_U A\) 即可。这个复杂度是 \(\sum_{i = 0}^n C(n, i) 2^i 2^{n - i} = 4^n\) 的，但常数小，可以过。
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;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#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 eb emplace_back
#define pb pop_back
#define pcnt(a) __builtin_popcount(a)
const int N = 15 + 1, M = 1 << 15 | 3, mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, C, t1, t2, ans, a[N], to[N], p[N], mp[N];
int f[M], g[N][M];
unordered_map<int,int> dp[M];
int qp(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
} return ret;
}
inline int norm(int a) {
a >= mod ? a -= mod : 0; return a;
}
signed main() {
file(graph);
cin >> n >> m >> C;
rep(i,0,n-1) cin >> a[i], ++ a[i];
iota(p, p + n, 0);
sort(p, p + n, [&](auto i, auto j){return a[i] < a[j];});
rep(i,0,n-1) mp[p[i]] = i;
sort(a, a + n);
rep(i,1,m) {
cin >> t1 >> t2, t1 = mp[t1 - 1], t2 = mp[t2 - 1];
to[t1] |= (1 << t2), to[t2] |= (1 << t1);
}
rep(t,0,n - 1) {
g[t][1 << t] = 1;
rep(S,0,(1<<t)-1) {
int S2 = S | (1 << t), Si = ((1 << t) - 1) ^ S;
f[S2] = norm(f[S2] + g[t][S2]);
for (int s = Si; s; s = Si & (s - 1)) {
if ((to[t] & s) and (s & -s) < (S2 & -S2))
g[t][S2 | s] = norm(g[t][S2 | s] - 1ll * g[t][S2] * f[s] % mod + mod);
}
}
}
dp[0][0] = 1;
rep(S,0,(1<<n)-1) {
int Si = ((1<<n)-1) ^ S, lb = (Si & -Si);
Si ^= lb;
for (auto [j, w] : dp[S]) if (w) {
for (int s = Si, sv; ; s = (s - 1) & Si) {
sv = s | lb;
if (pcnt(sv) & 1) dp[S | sv][j | lb] = norm(dp[S | sv][j | lb] + 1ll * dp[S][j] * f[sv] % mod);
else dp[S | sv][j] = norm(dp[S | sv][j] + 1ll * dp[S][j] * f[sv] % mod * (lb ? a[__lg(lb)] % mod : 0) % mod);
if (!s) break;
}
}
}
if (C == 0) ans = dp[(1 << n) - 1][0];
rep(S,1,(1<<n)-1) {
int tot = 0;
pre(t,60,0) {
int s = 0;
rep(i,0,n-1) if (S >> i & 1) s ^= a[i] >> (t + 1);
if (s != (C >> (t + 1))) break;
int c1 = 1, c2 = 0, c3 = 1, c4 = 0, V = (1ll << t) - 1;
rep(i,0,n-1) {
if (!(S >> i & 1)) continue;
int tmp = (a[i] & V) % mod, tmp2 = (V + 1) % mod;
if (!(a[i] >> t & 1)) {
c1 = 1ll * tmp * c1 % mod;
c2 = 1ll * tmp * c2 % mod;
} else {
c4 ^= 1;
int _c1 = c1, _c2 = c2;
c1 = norm(1ll * tmp * _c2 % mod + 1ll * tmp2 * _c1 % mod);
c2 = norm(1ll * tmp * _c1 % mod + 1ll * tmp2 * _c2 % mod);
} c3 = 1ll * tmp * c3 % mod;
}
if (c4) c2 = norm(c2 - c3 + mod);
else c1 = norm(c1 - c3 + mod);
if (!(C >> t & 1)) tot = norm(tot + 1ll * c1 * qp((V + 1) % mod, mod - 2) % mod);
else tot = norm(tot + 1ll * c2 * qp((V + 1) % mod, mod - 2) % mod);
} ans = norm(ans + 1ll * dp[(1 << n) - 1][S] * tot % mod);
}
cout << ans << '\n';
}