打开题一看，咦，两道数数，一道猫式树题
感觉树题不可做呀，暴力走人
数数题数哪个呢？感觉置换比矩阵好一些
于是数了数第一题
100 + 0 + 15 = 115
T1 bishop
给若干个环，这些环上一共有 $n$ 个点，在这 $k$ 个点上等概率放 $k$ 个人，一个点最多放一个人，求每个环都至少有一个点的概率，膜 998244353
$n,k leq 10^5$
sol：
考虑生成函数，一个环如果有 $size$ 个点，它的答案的生成函数 $F = sum_{k=1}^nC_{size}^{k} x^k$
然后把所有生成函数卷起来就可以了，考虑所有生成函数长度加起来只有 $n$ ，用分治或者堆来优化卷积即可
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn = 300010,mod = 998244353,G = 3,iG = 332748118; int R[maxn]; int A[maxn],B[maxn]; int n,k,p[maxn],size[maxn],vis[maxn]; int fac[maxn],ifac[maxn],lg[maxn]; vector<int> poly[maxn]; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } inline int C(int x,int y){return 1LL * fac[x] * ifac[y] % mod * ifac[x-y] % mod;} inline int ksm(int x,int t) { int res = 1; while(t) { if(t & 1) res = ((LL)res * (LL)x) % mod; x = ((LL)x * (LL)x) % mod; t >>= 1; } return res; } inline void fft_init(int len){for(int i=0;i<len;i++) R[i] = (R[i>>1] >> 1) | ((i & 1) << (lg[len] - 1));} inline void fft(int *a,int f,int len) { for(int i=0;i<len;i++)if(i < R[i])swap(a[i],a[R[i]]); for(int i=1;i<len;i<<=1) { int wn = ksm(((f == 1) ? G : iG),(mod - 1) / (i << 1)); for(int j=0;j<len;j+=(i<<1)) { int w = 1; for(int k=0;k<i;k++,w=((LL)w * (LL)wn) % mod) { int x = a[j + k], y = ((LL)w * (LL)a[j + k + i]) % mod; a[j + k] = (x + y) % mod; a[j + k + i] = (x - y + mod) % mod; } } } if(f == -1) { int inv = ksm(len,mod - 2); for(int i=0;i<len;i++)a[i] = ((LL)a[i] * (LL)inv) % mod; } } int mul(int *A,int *B,int len) { fft_init(len); fft(A,1,len); // for(int i=0;i<len;i++)cout<<A[i]<<" "; // cout<<endl; fft(B,1,len); for(int i=0;i<len;i++)A[i] = (LL)A[i] * B[i] % mod; fft(A,-1,len); --len;while(!A[len])--len; return len; } int solve(int l,int r) { if(l == r)return poly[l].size() - 1; int mid = (l + r) >> 1; int ls = solve(l,mid),rs = solve(mid + 1,r); int L = 1; for(;L <= ls + rs;L <<= 1); for(int i=0;i<=ls;i++)A[i] = poly[l][i]; for(int i=ls+1;i<L;i++)A[i] = 0; for(int i=0;i<=rs;i++)B[i] = poly[mid + 1][i]; for(int i=rs+1;i<L;i++)B[i] = 0; poly[l].clear();poly[mid + 1].clear(); L = mul(A,B,L); for(int i=0;i<=L;i++)poly[l].push_back(A[i]); return L; } int main() { freopen("bishop.in","r",stdin); freopen("bishop.out","w",stdout); fac[0] = 1;lg[0] = -1; for(int i=1;i<maxn;i++)lg[i] = lg[i >> 1] + 1; for(int i=1;i<maxn;i++)fac[i] = (1LL * fac[i - 1] * i) % mod; ifac[maxn - 1] = ksm(fac[maxn - 1],mod - 2); for(int i=maxn-2;i>=0;i--)ifac[i] = (1LL * ifac[i + 1] * (i + 1)) % mod; int T = read(); while(T--) { n = read(),k = read(); int top = 0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)p[i] = read(); for(int i=1;i<=n;i++) { if(vis[i])continue; int cnt = 0,tmp = i; while(!vis[tmp]) { vis[tmp] = 1; cnt++; tmp = p[tmp]; }size[++top] = cnt; } for(int i=1;i<=top;i++) { poly[i].push_back(0); for(int j=1;j<=size[i];j++)poly[i].push_back(C(size[i],j)); } solve(1,top); printf("%lld ",(LL)poly[1][k] * ksm(C(n,k),mod-2) % mod); poly[1].clear(); } }
T2 decoration
给 $S1$ 个 $1 imes 2$ 的骨牌，$S2$ 个 $2 imes 1$ 的骨牌，你要铺 $m imes n$ 的棋盘，对于所有 $n in [L,R]$，你要求出铺棋盘方案数的和，膜 998244353
$m leq 8,R 的位数 leq 2500$
sol：
n 很很小的时候是一个经典的轮廓线 dp
n 很小的时候用矩阵乘法加速转移，预处理 $f_{(i,S)}$ 到 $f_{(i+1,S')}$ 的转移矩阵，用 dfs 搜出转移矩阵就可以了，注意到本题要求前缀和，要多加一列表示前缀和，注意这个“很小”也可能很大，需要 10 进制快速幂，在 10 进制快速幂的同时，还需要把 10 拆成 2,4,8 ，在拆成 2,4,8 的同时，还需要把状态搜一下，把不能到达的状态都去除掉，要不然常数过大还是会被卡，好 duliu 啊 QAQ
n 很大的时候常系数线性递推式，算出特征多项式，多项式取膜或者暴力膜一下
这样就可以在 $k^2logn + k^4$ （$k$ 为特征多项式项数）时间里搞出矩阵 $A^n$
现在的问题就是怎么求特征多项式
插一插 / 消一消 / 行列式求一求即可
这一步是 $k^3$ 的
于是总复杂度就是 $O(8^m + k^2logn + k^4)$
#include <bits/stdc++.h> #define LL long long #define int long long using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f; for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0'; return x * f; } const int mod = 998244353; int m, sa, sb, SIZE, PSIZE; char l[2600], r[2600]; struct Matrix { int a[300][300]; Matrix() { memset(a, 0, sizeof(a)); } Matrix operator*(const Matrix& b) const { Matrix res; for (int i = 1; i <= SIZE; i++) for (int j = 1; j <= SIZE; j++) for (int k = 1; k <= SIZE; k++) (res.a[i][j] += (1LL * a[i][k] * b.a[k][j] % mod)) %= mod; return res; } } init; struct Poly { // force int a[600]; Poly() { memset(a, 0, sizeof(a)); } Poly operator+(const Poly& b) const { Poly c; for (int i = 0; i <= PSIZE + PSIZE; i++) c.a[i] = ((LL)a[i] + (LL)b.a[i]) % mod; return c; } Poly operator*(const Poly& b) const { Poly c; for (int i = 0; i <= PSIZE; i++) for (int j = 0; j <= PSIZE; j++) (c.a[i + j] += (1LL * a[i] * b.a[j] % mod)) %= mod; return c; } Poly operator%(const Poly& b) const { Poly c; for (int i = 0; i <= PSIZE + PSIZE; i++) c.a[i] = a[i]; for (int i = PSIZE; ~i; i--) { if (c.a[i + PSIZE] == 0) continue; for (int j = 0; j <= PSIZE; j++) c.a[i + j] = (c.a[i + j] + mod - (LL)c.a[i + PSIZE] * b.a[j] % mod) % mod; } return c; } Poly operator*(const int& b) const { Poly c; for (int i = 0; i <= PSIZE + PSIZE; i++) c.a[i] = 1LL * a[i] * b % mod; return c; } }; inline int skr(int x, int t) { int res = 1; while (t) { if (t & 1) res = 1LL * res * x % mod; x = 1LL * x * x % mod; t = t >> 1; } return res; } inline int det(Matrix x, int n) { int ret = 1; for (int i = 1; i <= n; i++) { int k = i; for (int j = i; j <= n; j++) if (x.a[j][i]) { k = j; break; } if (i != k) ret *= -1, swap(x.a[i], x.a[k]); int inv = skr(x.a[i][i], mod - 2); for (int j = i + 1; j <= n; j++) { int cur = 1LL * inv * x.a[j][i] % mod; for (int k = n; k >= i; k--) { (x.a[j][k] -= (cur * x.a[i][k] % mod)) %= mod; (x.a[j][k] += mod) %= mod; } } } for (int i = 1; i <= n; i++) ret = 1LL * ret * x.a[i][i] % mod; return (ret + mod) % mod; } int st, nx[300], cur[300], tr[300][300], ma[300][300]; int hsh[300]; inline void dfs(int pos, int s_a, int s_b) { if (pos == m + 1) { int pre = 0, flag = 1, res = 1; for (int i = 1; i <= m; i++) if (!cur[i]) flag = 0; for (int i = 1; i <= m; i++) if (nx[i]) pre |= (1 << (i - 1)); for (int i = 1; i <= s_a; i++) res = 1LL * res * sa % mod; for (int i = 1; i <= s_b; i++) res = 1LL * res * sb % mod; if (flag) { tr[pre][st] = 1; (ma[pre][st] += res) %= mod; } return; } nx[pos] = 0; dfs(pos + 1, s_a, s_b); if (!cur[pos]) { nx[pos] = cur[pos] = 1; dfs(pos + 1, s_a + 1, s_b); nx[pos] = cur[pos] = 0; } if (pos != 1 && (!nx[pos - 1])) { nx[pos] = nx[pos - 1] = 1; dfs(pos + 1, s_a, s_b + 1); nx[pos] = nx[pos - 1] = 0; } } Poly prek[600], sufk[600], p[600], t; int v[600]; void make(Matrix A) { PSIZE = SIZE; prek[0].a[1] = 1; for (int i = 1; i <= PSIZE; i++) { t.a[0] = mod - i; t.a[1] = 1; prek[i] = prek[i - 1] * t; } sufk[PSIZE + 1].a[0] = 1; for (int i = PSIZE; i >= 1; i--) { t.a[0] = mod - i; t.a[1] = 1; sufk[i] = sufk[i + 1] * t; } Matrix B; for (int x = 0; x <= PSIZE; x++) { for (int i = 1; i <= PSIZE; i++) for (int j = 1; j <= PSIZE; j++) B.a[i][j] = (A.a[i][j] - x * (i == j ? 1 : 0) + mod) % mod; v[x] = det(B, PSIZE); for (int j = 0; j <= PSIZE; j++) if (x != j) v[x] = (LL)v[x] * skr(x - j + mod, mod - 2) % mod; if (!x) p[x] = sufk[1]; else if (x == PSIZE) p[x] = prek[PSIZE - 1]; else p[x] = sufk[x + 1] * prek[x - 1]; p[x] = p[x] * v[x]; } memset(t.a, 0, sizeof(t.a)); for (int i = 0; i <= PSIZE; i++) t = t + p[i]; int Inv = skr(t.a[PSIZE], mod - 2); for (int i = 0; i <= PSIZE; i++) t.a[i] = (LL)t.a[i] * Inv % mod; } void Add(Matrix& A, Matrix& B, int v) { for (int i = 1; i <= SIZE; i++) for (int j = 1; j <= SIZE; j++) { (A.a[i][j] += (LL)B.a[i][j] * v % mod) %= mod; } } void Qpow(Matrix& C, char* M, int extra) { Poly ret, tmp, tmp2; memset(ret.a, 0, sizeof(ret.a)); memset(tmp.a, 0, sizeof(tmp.a)); ret.a[0] = 1; tmp.a[1] = 1; int m = strlen(M); for (int i = m - 1; ~i; i--) { int add = M[i] - '0'; if (add & 1) ret = (ret * tmp) % t; tmp = (tmp * tmp) % t; tmp2 = tmp; if (add & 2) ret = (ret * tmp) % t; tmp = (tmp * tmp) % t; if (add & 4) ret = (ret * tmp) % t; tmp = (tmp * tmp) % t; if (add & 8) ret = (ret * tmp) % t; tmp = (tmp2 * tmp) % t; } Matrix B; for (int i = 1; i <= SIZE; i++) for (int j = 1; j <= SIZE; j++) B.a[i][j] = (i == j ? 1 : 0); memset(C.a, 0, sizeof(C.a)); for (int i = 0; i <= SIZE; i++) { Add(C, B, ret.a[i]); B = B * init; } if (extra) C = C * init; } int calc(char* l, int extra) { Matrix tmp; Qpow(tmp, l, extra); return tmp.a[SIZE][SIZE - 1]; } signed main() { freopen("decoration.in", "r", stdin); freopen("decoration.out", "w", stdout); scanf("%s%s", &l, &r); m = read(), sa = read(), sb = read(); int mx = (1 << m); SIZE = mx; for (int S = 0; S < mx; S++) { for (int j = 1; j <= m; j++) cur[j] = S >> j - 1 & 1; st = S; dfs(1, 0, 0); } for (int k = 0; k < mx; k++) for (int i = 0; i < mx; i++) for (int j = 0; j < mx; j++) tr[i][j] |= (tr[i][k] & tr[k][j]); int dfn = 0; for (int S = 0; S < mx; S++) if (tr[S][SIZE - 1]) hsh[S] = ++dfn; SIZE = dfn + 1; for (int i = 0; i < mx; i++) for (int j = 0; j < mx; j++) if (hsh[i] && hsh[j]) init.a[hsh[i]][hsh[j]] = ma[i][j]; init.a[SIZE][SIZE] = init.a[SIZE][SIZE - 1] = 1; make(init); LL res = calc(r, 1) - calc(l, 0); printf("%lld ", (res + mod) % mod); }
T3 conference
给一棵有边权的树，每个点有若干个人，每次修改一个点的人数，或者求一条链的带权中位数节点
$n,q leq 10^5$
sol：
需要一个数据结构维护
1.单点修改
2.求一条链的带权中位数节点
3.求一条链上所有点到某一点的带权距离和
先考虑 1.+3.
显然一条路径可以分为 $x ightarrow lca ightarrow y$
对于一个靠近 $x$ （在 $x ightarrow lca$ 路径上）的点 $z$
它到 $x$ 这一段的答案就是 $sum_{v in path}dep_i imes s_i - sum_{v in path} imes dep_z$
靠近 $y$ 的也差不多
转换成差分，dfs 序树状数组即可
然后考虑 2.
二分一波，考虑要求的答案就是“第一个 $x => a$ 使得权值超过整条链权值一半的 $a$ 点”
用刚才的 1. + 3. 来 check 一下就可以了
复杂度 $O(nlog^2n)$
也可以 LCT 大常数 $O(nlogn)$
#include <bits/stdc++.h> #define LL long long using namespace std; inline LL read() { LL x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f; for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0'; return x * f; } const int maxn = 160000; int n, q; LL a[maxn]; // LCA int first[maxn], to[maxn << 1], nx[maxn << 1], val[maxn << 1], cnt; inline void add(int u, int v, int w) { to[++cnt] = v; nx[cnt] = first[u]; first[u] = cnt; val[cnt] = w; } inline void ins(int u, int v, int w) { add(u, v, w); add(v, u, w); } int dep[maxn], anc[maxn][23], ind[maxn], oud[maxn], ToT; LL dis[maxn]; inline void dfs(int x) { for (int i = 1; i <= 22; i++) anc[x][i] = anc[anc[x][i - 1]][i - 1]; ind[x] = ++ToT; for (int i = first[x]; i; i = nx[i]) { if (to[i] == anc[x][0]) continue; dep[to[i]] = dep[x] + 1; dis[to[i]] = dis[x] + val[i]; anc[to[i]][0] = x; dfs(to[i]); } oud[x] = ToT; } inline int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); int t = dep[x] - dep[y]; for (int i = 0; i <= 22; i++) if (t & (1 << i)) x = anc[x][i]; if (x == y) return x; for (int i = 22; ~i; i--) if (anc[x][i] != anc[y][i]) { x = anc[x][i]; y = anc[y][i]; } return anc[x][0]; } // LCA END // Fenwick inline LL lowbit(LL x) { return x & (-x); } struct Fenwick { LL c[maxn]; Fenwick() { memset(c, 0, sizeof(c)); } inline void add(int pos, LL val) { for (; pos <= n; pos += lowbit(pos)) c[pos] += val; } inline LL ask(int pos) { LL res = 0; for (; pos; pos -= lowbit(pos)) res += c[pos]; return res; } inline void Tradd(int pos, LL val) { add(ind[pos], val); add(oud[pos] + 1, -val); } } t1, t2; inline LL qt1(int x, int y) { int l = lca(x, y); return t1.ask(ind[x]) + t1.ask(ind[y]) + a[l] - (t1.ask(ind[l]) << 1); } inline LL qt2(int x, int y) { int l = lca(x, y); return t2.ask(ind[x]) + t2.ask(ind[y]) + (a[l] * dis[l]) - (t2.ask(ind[l]) << 1); } // Fenwick END void update(int x, int y) { t1.Tradd(x, y - a[x]); t2.Tradd(x, dis[x] * (y - a[x])); a[x] = y; } LL query(int x, int y) { int l = lca(x, y), targ; LL exp_val = ((qt1(x, y) + 1) >> 1), ret = 0; int On_left = 0; if (a[x] >= exp_val) targ = x, On_left = 1; else if (qt1(x, y) - a[y] < exp_val) targ = y; else { if (qt1(x, l) >= exp_val) { int cur = x; for (int i = 22; ~i; i--) if ((qt1(anc[cur][i], x) < exp_val) && (dep[l] <= dep[anc[cur][i]])) cur = anc[cur][i]; targ = anc[cur][0]; On_left = 1; } else { int cur = y; for (int i = 22; ~i; i--) if ((qt1(anc[cur][i], y) < exp_val) && (dep[l] <= dep[anc[cur][i]])) cur = anc[cur][i]; targ = anc[cur][0]; } } if (!On_left) swap(x, y); ret += qt2(x, targ) - qt1(x, targ) * dis[targ]; ret -= qt2(targ, l) - qt1(targ, l) * dis[targ]; ret += qt2(y, l) + qt1(y, l) * (dis[targ] - 2 * dis[l]); ret -= (dis[targ] - dis[l]) * a[l]; return ret; } int main() { freopen("conference.in", "r", stdin); freopen("conference.out", "w", stdout); n = read(); for (int i = 1; i <= n; i++) a[i] = read(); for (int i = 2; i <= n; i++) { int u = read(), v = read(), w = read(); ins(u, v, w); } dep[1] = 1; dfs(1); for (int i = 1; i <= n; i++) { int t = a[i]; a[i] = 0; update(i, t); } q = read(); while (q--) { int tp = read(), x = read(), y = read(); if (tp == 2) update(x, y); else printf("%lld ", query(x, y)); } }