提高组杂题训练1

A [USACO22DEC] Breakdown P

首先 \(N\le300\) \(k\le8\) 看样子复杂度是个 3 次的东西。一些套路的东西比如删边改加边不说了。这个 \(K\le8\) 很有讲究。

首先，不妨折半一下，算出从 1 经过一半条边到 \(u\) 的最短路径和 \(u\) 到 \(n\) 的最短路径，那么答案就可以 \(\mathcal{O}(n)\) 合并。对于 \(k'\le 4\) ，可以维护两个数组 \(f[u][v]\) 和 \(g[u][v]\)，分别表示 \(u\sim v\) 走一条边和走两条边的最短路，维护 \(h[u]\) 数组表示从起始节点到 \(u\) 经过 \(k'\) 条边的最短路径。可以惊人的发现 1 和 2 可以凑出所有 4 以内的情况！！当加入边 \(u, v\) 时，当且仅当 \(u\) 为 \(bg\) 的时候需要枚举所有断点维护 \(h\)，所以加边操作均摊 \(\mathcal{O}(n)\)。总复杂度 \(\mathcal{O}(N^3)\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 305;
int n, k, x[N*N], y[N*N], ans[N*N], edge[N][N];
struct XiaoLe{int f[N][N], g[N][N], h[N], fk, bg;const int& operator [](const int x) const { return h[x]; }inline void build(int kf, int gb){fk = kf; bg = gb;memset(f, 0x3f, sizeof(f));if(fk > 1) memset(g, 0x3f, sizeof(g));memset(h, 0x3f, sizeof(int)*(n+1));if(!fk) h[bg] = 0;}inline void add(int u, int v, int val){if(!fk) return;if(fk == 1){if(u ^ bg) return;h[v] = min(h[v], val);return;}f[u][v] = val;for(int i=1; i<=n; ++i){g[i][v] = min(g[i][v], f[i][u] + val);g[u][i] = min(g[u][i], val + f[v][i]);}if(fk == 2){for(int i=1; i<=n; ++i)h[i] = min(h[i], g[bg][i]);} else if(fk == 3){if(u == bg){for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)h[i] = min(h[i], f[bg][j] + g[j][i]);} else{for(int i=1; i<=n; ++i){h[i] = min({h[i], g[bg][u] + f[u][i], g[bg][v] + f[v][i]});h[u] = min(h[u], f[bg][i] + g[i][u]);h[v] = min(h[v], f[bg][i] + g[i][v]);}}} else{if(u == bg){for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)h[i] = min(h[i], g[bg][j] + g[j][i]);} else {for(int i=1; i<=n; ++i){h[i] = min({h[i], g[bg][u] + g[u][i], g[bg][v] + g[v][i]});h[u] = min(h[u], g[bg][i] + g[i][u]);h[v] = min(h[v], g[bg][i] + g[i][v]);}}}}
} m1, mn;
signed main(){ios::sync_with_stdio(0), cout.tie(0), cout.tie(0);cin>>n>>k; int nn = n * n;for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)cin>>edge[i][j];m1.build(k >> 1, 1), mn.build((k + 1) >> 1, n); memset(ans, 0x3f, sizeof(int)*(nn+1));for(int i=1; i<=nn; ++i) cin>>x[i]>>y[i];for(int i=nn, u, v; i>=1; --i){for(int j=1; j<=n; ++j)ans[i] = min(ans[i], m1[j] + mn[j]);ans[i] = ans[i] > 1e9 ? -1 : ans[i];u = x[i], v = y[i];m1.add(u, v, edge[u][v]);mn.add(v, u, edge[u][v]);}for(int i=1; i<=nn; ++i) cout<<ans[i]<<'\n';return 0;
}

B [USACO22DEC] Making Friends P

按时间模拟，对每个节点维护 set 表示当前节点都和谁是朋友关系，每次删掉一个节点之后，ans 就加上 size，并把新建立的朋友关系加到下一个最先走掉的节点的 set 里。相当于维护一个集合，也可以使用线段树合并。最后 ans -= m。

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
int n, m; long long ans;
set<int> st[N];
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m; ans = -m;for(int i=1, u, v; i<=m; ++i){cin>>u>>v; if(u > v) swap(u, v);st[u].insert(v);}for(int i=1; i<=n; ++i){if(st[i].empty()) continue;ans += st[i].size();int u = *st[i].begin(), v = i;st[i].erase(st[i].begin());if(st[u].size() < st[v].size()) swap(st[u], st[v]);for(int it : st[v]) st[u].insert(it);} return cout<<ans<<'\n', 0;
}

C [USACO22DEC] Palindromes P

分析一下回文串的性质，因为只有两种字符，所以很好分析，这两种字符就用 \(0\) \(1\) 代替了，并且只要 \(1\) 满足性质，\(0\) 必然满足，所以只分析 \(1\) 即可。

对于一个串 \([L,R]\) ，它是轴对称的，并且对称中心为一个或者两个 \(1\)，不妨枚举所有对称中心并扩展。假如扩展的两个 \(1\) 分别为 \(l\) 和 \(r\)，那么这俩关于对称中心的充要条件即为 \(l+r=L+R\)，那么移动步数为 \(|L+R-(l+r)|\)。那么每次扩展两个 \(1\)，就把它的权值加到树状数组里维护即可。复杂度 \(\mathcal{O}(N^2\log N)\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 7505;
string s; int n, ans, g[N], cnt;
struct BIT{#define lb ((i) & (-i))int t[N<<1];inline void add(int x, int val){for(int i=x; i<=n*2; i+=lb) t[i] += val;}inline int qry(int x){int ans = 0;for(int i=x; i; i-=lb) ans += t[i];return ans;}
} t1, t2;
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>s; n = s.size();for(int i=1; i<=n; ++i) if(s[i-1] == 'G') g[++cnt] = i;g[cnt+1] = n+1;for(int i=1, x=1, y=1; i<=cnt; ++i, x=i, y=i){int sum = 0, nm = 0;while(1 <= x && y <= cnt){int tot = g[x] + g[y];if(x != i) t1.add(tot, tot), t2.add(tot, 1), sum += tot, ++nm;for(int l=g[x]; l>g[x-1]; --l) for(int r=g[y]; r<g[y+1]; ++r){if((r - l) & 1){ --ans; continue; }tot = l + r;int val = t1.qry(tot-1), num = t2.qry(tot-1);ans += llabs((tot >> 1) - g[i]);ans += num * tot - val + sum - val - tot * (nm - num);} --x, ++y;}memset(t1.t, 0, sizeof(int) * (2*n + 1));memset(t2.t, 0, sizeof(int) * (2*n + 1));}for(int i=1, x=1, y=2; i<cnt; ++i, x=i, y=i+1){int sum = 0, nm = 0;while(1 <= x && y <= cnt){int tot = g[x] + g[y];t1.add(tot, tot), t2.add(tot, 1), sum += tot, ++nm;for(int l=g[x]; l>g[x-1]; --l) for(int r=g[y]; r<g[y+1]; ++r){tot = l + r;int val = t1.qry(tot-1), num = t2.qry(tot-1);ans += (num * tot - val) + sum - val - tot * (nm - num);} --x; ++y;}memset(t1.t, 0, sizeof(int) * (2*n + 1));memset(t2.t, 0, sizeof(int) * (2*n + 1));} return cout<<ans, 0;
}

D [USACO23JAN] Tractor Paths P

神一样的倍增，屎一样的题面，对着题目瞪了有半个多小时……

不会倍增，看了题解，太™强拉！！！

首先，这些区间的左端点和右端点单调递增，所以如果想知道一个区间最远能到达哪里，就贪心地往最右边走就好了。所以可以使用倍增优化此过程。这是第一个答案求法。

对于第二问，维护特殊拖拉机的前缀和的倍增数组，沿着你倍增过来的路线加贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define p pair<int, int>
constexpr int N = 2e5 + 5;
int n, m, L[N], R[N], lt[20][N], rt[20][N], sl[20][N], sr[20][N], sum[N];
string s1, s2;
inline int Dis(int u, int v){if(u == v) return 0;int dis = 0;for(int i=__lg(n); i>=0; --i) if(lt[i][u] != -1 && lt[i][u] < v)dis |= (1<<i), u = lt[i][u];return dis + 1;
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m>>s1>>s2;for(int i=1, cnt=0, now=1; i<=n<<1; ++i){if(s1[i-1] == 'L') ++cnt;else R[now++] = cnt; }for(int i=n<<1, cnt=n+1, now=n; i>=1; --i){if(s1[i-1] == 'R') --cnt;else L[now--] = cnt;}for(int i=1; i<=n; ++i) sum[i] = sum[i-1] + s2[i-1] - '0';memset(lt, 0xff, sizeof(lt)); memset(rt, 0xff, sizeof(rt));for(int i=1; i<=n; ++i) lt[0][i] = R[i], sl[0][i] = sum[R[i]];for(int i=1; i<=n; ++i) rt[0][i] = L[i], sr[0][i] = sum[L[i]-1];for(int i=1; i<=__lg(n); ++i) for(int j=1; j<n; ++j) if(lt[i-1][j] > 0){lt[i][j] = lt[i-1][lt[i-1][j]];if(lt[i][j] > 0) sl[i][j] = sl[i-1][j] + sl[i-1][lt[i-1][j]];}for(int i=1; i<=__lg(n); ++i) for(int j=n; j>1; --j) if(rt[i-1][j] > 0){rt[i][j] = rt[i-1][rt[i-1][j]];if(rt[i][j] > 0) sr[i][j] = sr[i-1][j] + sr[i-1][rt[i-1][j]];}while(m--){int u, v, dis; cin>>u>>v;cout<<(dis = Dis(u, v))<<' '; --dis;int ans = s2[u-1] - '0' + s2[v-1] - '0';if(u == v){ cout<<ans; continue; }for(int i=__lg(n); i>=0; --i) if(dis & (1<<i))ans += sl[i][u], u = lt[i][u];for(int i=__lg(n); i>=0; --i) if(dis & (1<<i))ans -= sr[i][v], v = rt[i][v];cout<<ans<<'\n';} return 0;
}

E [USACO23JAN] Mana Collection P

很巧妙的一道题

首先可以发现，当走过的点集确定之后，答案的大小仅与每个节点最后走到的时间有关，即为（\(d_i\) 为最后遍历的时间）：

\[ans=\sum_{i=1}^{k}val_i*d_i \]

而贪心的说，对于每个节点的最后遍历时间越大，答案也就越大。一个节点的最短最后遍历时间即为 \(d_i=s-\sum_\limits{j=i}^{k-1}dis_{j,j+1}\)，其中 \(dis\) 为两点间最短路径。那么带入刚才的狮子可得：

\[ans = s{\large \sum_{i = 1}^{k}} val[i]-{\large \sum_{i = 1}^{k-1}}dis(c_i, c_{i+1})\sum_{j = 1}^{i}val[j] \]

右边那一坨拿状压爆搞即可。

维护凸包或者使用李超线段树即可。复杂度 \(\mathcal{O}(N^3+N^22^N+q\log n)\)。说句闲话：我想用离线查询 + 单队维护凸包搞，于是调了一个下午和晚上（还没调出来）。有李超这么nb玩意，凸包🐶都不用！！！

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 5e6 + 5, S = 1 << 18, Inf = 1e18;
int n, m, q, tot, val[20], dis[20][20], sum[S], f[19][S], cnt[19], rt[19];
inline void init(){for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j) if(i ^ j) dis[i][j] = Inf;for(int j=0; j<tot; ++j) f[i][j] = Inf;}
}
namespace LCST{struct Seg{int k, b;int operator () (const int x) const{ return k * x + b; }}s[N];int cnt, tot, t[N], ls[N], rs[N];inline void modify(int& id, int l, int r, int w){if(!id) return void(t[id = ++cnt] = w);if(l == r) return void(s[w](l) > s[t[id]](l) ? t[id] = w : 0);int mid = (l + r) >> 1;if(s[w](mid) > s[t[id]](mid)) swap(w, t[id]);if(s[w](l) >= s[t[id]](l)) modify(ls[id], l, mid, w);if(s[w](r) >= s[t[id]](r)) modify(rs[id], mid+1, r, w);}inline int query(int id, int l, int r, int x){if(!id) return 0;int ans = s[t[id]](x), mid = (l + r) >> 1;if(x <= mid) ans = max(ans, query(ls[id], l, mid, x));else ans = max(ans, query(rs[id], mid+1, r, x));return ans;}inline void push_in(int &rt, int k, int b){s[++tot] = Seg{k, b};modify(rt, 1, 1e9, tot);}
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m; tot = 1 << n; init();for(int i=1; i<=n; ++i) cin>>val[i];for(int i=1, u, v, w; i<=m; ++i)cin>>u>>v>>w, dis[u][v] = w;for(int k=1; k<=n; ++k) for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j)if((k ^ i) && (k ^ j) && (i ^ j))dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);for(int s=1; s<tot; ++s){for(int i=1; i<=n; ++i) if(s & (1<<(i-1))){sum[s] += val[i];int tmp = s ^ (1 << (i-1));if(!tmp){ f[i][s] = 0; break; }for(int k=1; k<=n; ++k) if(tmp & (1<<(k-1))){if(dis[k][i] == Inf) continue;f[i][s] = min(f[i][s], f[k][tmp] + sum[tmp] * dis[k][i]);}}}for(int i=1; i<=n; ++i){for(int s=1; s<tot; ++s) if(s & (1<<(i-1))){if(f[i][s] >= Inf) continue;LCST::push_in(rt[i], sum[s], -f[i][s]);}} cin>>q; while(q--){int s, e; cin>>s>>e;cout<<LCST::query(rt[e], 1, 1e9, s)<<'\n';} return 0;
}

F [USACO23JAN] Subtree Activation P

这道题很好手模，很好发现的是：如果你想完成 \(u\) 和 \(v\) 节点以及他们的公共祖先 \(w\)，那么存在最有策略是依次点亮 \(u\sim w\sim v\) 及其子树，然后依次灭掉 \(u\sim w\sim v\) 的子树，这样同时完成了 \(u,w,v\) 的要求，可以得到的是，这样的最优操作次数恰好为 \(2siz_w\)。

当我还在苦逼找规律的时候，大神已经开始设计 DP 了。令 \(f_{u,0}\) 表示覆盖 \(u\) 的子树的最小操作次数。\(f_{u,1}\) 表示有且仅有一条从 \(u\) 到 \(u\) 的子树内某节点 \(v\) 的链没有被点亮，而 \(u\) 子树其他节点都被覆盖的最小次数。这样设计有个显而易见的好处：合并链的代价变得可计算。

• 对于 \(f_{u,1}\)，可以看成在 \(u\) 的儿子节点里找一个儿子并把它的链向上延长到 \(u\)，相应地，其它儿子及其子树都应该被覆盖过了。于是有：

  \[\begin{split} f_{u,1}&=\min_{v\in son_u}(f_{v,1}+\sum_{v'\in son_u,v'\not=v}f_{v',0}) \\ &=\sum_{v\in son_u}f_{v, 0}+\min_{v'\in son_u}(f_{v',1}-f_{v',0}) \end{split} \]

• 对于 \(f_{u,0}\)，分为两种情况：

  • 假设 \(u\) 的所有儿子及其子树都已经被覆盖过了，那么就找个儿子并把它的链延长至 \(u\) 并加上额外贡献。

    \[f_{u,0}=\sum_{v\in son_u}f_{v,0}+2(siz_u-\max_{v\in son_u}(siz_v)) \]

  • 假设 \(u\) 还有两个儿子没被覆盖，那么将这两个儿子的链延长到 \(u\) 然后一并统计一下贡献：

    \[\begin{split} f_{u,0}&=2siz_u+\min_{v_1\in son_u,v_2\in son_u,v1\not=v_2}(f_{v1,1}+f_{v2,1}+\sum_{v_3\in son_u,v_3\not=v_1,v_3\not=v_2}f_{v_3,0})\\ &=2siz_u+\sum_{v\in son_u}f_{v,0}+\min_{v_1\in son_u,v_2\in son_u,v1\not=v_2}(f_{v1,1}-f_{v1,0}+f_{v2,1}-f_{v2,0}) \end{split} \]

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2e5 + 5, Inf = 1e18;
int n, f[2][N], siz[N];
vector<int> G[N];
inline void dfs(int u){siz[u] = 1; if(!G[u].size()) return void(f[0][u] = 2);int mn1 = Inf, mn2 = Inf, sum = 0, mx = 0;for(int v : G[u]){dfs(v); siz[u] += siz[v];mx = max(mx, siz[v]);sum += f[0][v];int res = f[1][v] - f[0][v];if(mn1 > res) mn2 = mn1, mn1 = res;else if(mn2 > res) mn2 = res;}if(mn1 != Inf) f[1][u] = sum + mn1;f[0][u] = sum + 2*(siz[u] - mx);if(mn1 != Inf && mn2 != Inf)f[0][u] = min(f[0][u], 2*siz[u] + sum + mn1 + mn2);
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n; for(int i=2, fa; i<=n; ++i)cin>>fa, G[fa].push_back(i);dfs(1); return cout<<f[0][1], 0;
}

性质分析、题目转换、构造 DP一条龙。

G [USACO23FEB] Hungry Cow P

一眼线段树分治，但不知道如何实现把大的数改小的操作。动态开点维护每个节点的有干草的节点数和贡献不用说了，还要维护从左边传进来的干草数，以及右儿子的贡献。

因为修改每一天的干草数可能增大可能减小，所以标记是不能永久打在节点上面的。这是最重要的一点。

感觉这种题就是逢山开路，遇水搭桥那种的。在写的过程中，需要什么就维护什么。

#include<bits/stdc++.h>
using namespace std;
#define it __int128
#define int long long
constexpr int N = 5e6 + 5, M = 1e9 + 7, Inv2 = 5e8 + 4;
int q, rt;
namespace ST{int cnt;struct node{ int ls, rs, sum, num, rgt, pas; }t[N];inline int query(int id, int l, int r, int val){if(!val) return t[id].sum;if(l == r) return val ? l % M : t[id].sum;int mid = (l + r) >> 1, ls = t[id].ls, rs = t[id].rs;if(t[ls].num + val <= mid + 1 - l)return (query(ls, l, mid, val) + t[id].rgt) % M;int ans = (it)(l + mid) * (mid - l + 1) % M * Inv2 % M;ans = (ans + query(rs, mid+1, r, t[ls].num + val - (mid - l + 1) + t[ls].pas)) % M;return ans;}inline void pushup(int id, int l, int r){int ls = t[id].ls, rs = t[id].rs, mid = (l + r) >> 1;t[id].num = t[ls].num + min(t[rs].num + t[ls].pas, r - mid);t[id].pas = t[rs].pas + max(t[ls].pas + t[rs].num - (r - mid), 0ll);t[id].rgt = query(rs, mid+1, r, t[ls].pas);t[id].sum = (t[ls].sum + t[id].rgt) % M;}inline void modify(int &id, int l, int r, int pos, int val){if(!id) id = ++cnt;if(l == r){if(val) t[id].sum = l % M, t[id].num = 1, t[id].pas = val - 1;else t[id].sum = t[id].num = t[id].pas = 0;return;} int mid = (l + r) >> 1;if(pos <= mid) modify(t[id].ls, l, mid, pos, val);else modify(t[id].rs, mid+1, r, pos, val);pushup(id, l, r);}
} using namespace ST;
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>q; while(q--){int x, y; cin>>x>>y;modify(rt, 1, 2e14, x, y);cout<<t[rt].sum<<'\n';} return 0;
}

双倍经验 楼房重建

H [USACO23FEB] Problem Setting

感觉题意很好转化，就是先放一大堆 E 再放一大堆 H，当然，每一道题对于每一个验题人的难度不一定都相同。当放置一道题 \(i\) 的时候，第 \(i+1\) 道题必须是认为 \(i\) 题难的所有人都认为难的题。再联系到 \(m\le 20\)，我们可以找到一个点集 \(s\) 表示所有状态为 \(1\) 的验题人都觉得这道题难，那么 \(s\) 的上一个集合一定是 \(s\) 的一个子集。考虑维护出所有的点集 \(s\) 以及其对应的所有题目，然后状压 DP 转移，所有状态的方案数之和即为答案。拼尽全力也只能想到枚举子集的暴力 DP……

Warning：枚举子集一定要等枚举到 \(0\) 之后再 break 掉！！！

暴力 \(\mathcal{O}(3^m)\) 60pts

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 1e5 + 5, S = 1 << 20, M = 1e9 + 7;
int n, m, num[S], tot, sum[N], ans, f[S];
string str[21];
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m; tot = 1 << m; sum[1] = 1;for(int i=2; i<=n; ++i) sum[i] = ((ll)i + (ll)sum[i-1] * i % M) % M;for(int i=1; i<=m; ++i) cin>>str[i];for(int i=1; i<=n; ++i){int tmp = 0;for(int j=1; j<=m; ++j) if(str[j][i-1] == 'H')tmp |= 1 << (j-1);++num[tmp];}for(int s=0; s<tot; ++s) num[s] = sum[num[s]];ans = f[0] = num[0];for(int s=1; s<tot; ++s){f[s] = 1;for(int tmp=(s-1) & s; tmp>=0; tmp = (tmp-1) & s){f[s] = ((ll)f[s] + (ll)f[tmp]) % M;if(!tmp) break;}f[s] = (ll)f[s] * num[s] % M;ans = ((ll)ans + (ll)f[s]) % M;} return cout<<ans, 0;
}

官方正解 FMT，于是我就去学了一下。好的，这篇博客正式变成 FMT 学习笔记！

---

FMT 快速莫比乌斯变换（Fast Möbius Transform）

要求：

\[\hat{f}(S)=\sum_{T\subseteq S}f(T) \]

不知道咋读）定义：

\[\hat{f}(S,i)=\sum_{T\in S}f(T)[\{i+1,i+2,i+3,\dots ,n\}\subseteq S] \]

于是有 \(\hat{f}(S,0)=f(s)\) 、\(\hat{f}(S,|S|)=f(\varnothing)\)

设 \(S \cap \{i\}=\varnothing\)，所以 \(\hat{f}(S,i)=\hat{f}(S,i-1)\)。因为 \(\hat{f}(S,i)\) 表示 \(\{i+1,i+2,\dots,n\}\) 一定包含于 \(T\)，并且一定没有选 \(i\)，\(\hat{f}(S\cup \{i\},i-1)\) 表示 \(\{i+1,i+2,\dots,n\}\) 一定包含于 \(T\)，并且一定选择了 \(i\)。依据加法原理，那么有：

\[\hat{f}(S\cup\{i\},i)=\hat{f}(S,i-1)+\hat{f}(S\cup \{i\},i-1) \]

可以用 \(\mathcal{O}(n2^n)\) 的复杂度递推求解子集和。当然也可以求解单个 \(f(S)\)：

\[f(S)=\sum_{\{i\}\subseteq S}^{n}\hat{f}(\complement_{T}\{i\},i) \]

WC，刚看一篇博客说它可以理解为高维前缀和状物，一下子变得清晰了。我上面写的是 屎 (偏数学一点)。

对于求解一维前缀和，我们有：

for(int i=1; i<=n; ++i) s[i] += s[i-1];

对于二维，一般来说用的最多的是容斥，不过仍然可以一维一维地处理：

for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) s[i][j] += s[i-1][j];
for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) s[i][j] += s[i][j-1];

对于更高的维度也是如此。对于每一维都为 \(0,1\) 的维度，有：

for(int i=1; i<2; ++i) for(int j=1; j<2; ++j) ... s[i][j]... += s[i^1][j]...
...

不妨使用状压完成此过程，就有：

for(int i=0; i<(1<<n); ++i) for(int j=0; j<n; ++j)if(i & (1<<j)) s[i] += s[i^(1<<j)];

这不就是求子集和吗？FMT 正是利用此性质将复杂度大大的优化。

---

回到此题，那我们就可以在递推 \(\hat{f}\) 的同时处理出 \(f\) 数组，大大降低了枚举子集的复杂度。总复杂度 \(\mathcal{O}(m2^m)\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 1e5 + 5, S = 1 << 20, M = 1e9 + 7;
int n, m, num[S], tot, sum[N], ans, f[S], sf[21][S];
string str[21];
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m; tot = 1 << m; sum[1] = 1;for(int i=2; i<=n; ++i) sum[i] = ((ll)i + (ll)sum[i-1] * i % M) % M;for(int i=1; i<=m; ++i) cin>>str[i];for(int i=1; i<=n; ++i){int tmp = 0;for(int j=1; j<=m; ++j) if(str[j][i-1] == 'H')tmp |= 1 << (j-1);++num[tmp];}for(int s=0; s<tot; ++s) num[s] = sum[num[s]];for(int s=0; s<tot; ++s){f[s] = 1;for(int i=0; i<m; ++i) if(s & (1<<i))f[s] = ((ll)f[s] + (ll)sf[i][s^(1<<i)]) % M;f[s] = (ll)f[s] * num[s] % M;ans = ((ll)ans + (ll)f[s]) % M; sf[0][s] = f[s];for(int i=1; i<m; ++i){sf[i][s] = sf[i-1][s];if(s & (1<<(i-1))) sf[i][s] = ((ll)sf[i][s] + (ll)sf[i-1][s^(1<<(i-1))]) % M;}} return cout<<ans, 0;
}

I [USACO23FEB] Watching Cowflix P

一眼虚树好吧，然后不会。看了题解的虚树做法，对于我这种菜鸡不可做，考虑根号分治。

首先有树形 DP。令 \(f_{1/0,i}\) 表示 \(i\) 在或不在联通块内。那么有：

\[\begin{split} f_{0,u}&=\sum_{v\in son_u}min(f_{0,v},f_{1, v}+k)\\ f_{1,u}&=\sum_{v\in son_u}min(f_{1,v},f_{0,v}) \end{split} \]

DP需要使用 DFS序优化。暴力巨好打。然后打表可知，答案是单调不降的，并且相邻两个答案之间的差值也是单调不降的。观察到对于 \(\sqrt n\) 以内的答案差值变化较大，直接暴力处理。当 \(k>\sqrt n\) 之后答案差值变化较小且连续，直接二分找到每一个差值相等的区间求解即可。码好打。这题还能这么做！！！

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5, Inf = 1e9;
int n, f[2][N], rnk[N], tot, fa[N];
string str; vector<int> G[N];
inline void dfs(int u, int f){rnk[++tot] = u;for(int v : G[u]){if(v == f) continue;fa[v] = u; dfs(v, u);}
}
inline int solve(int k){for(int i=1; i<=n; ++i)f[1][i] = 1, f[0][i] = str[i-1] == '0' ? 0 : Inf;for(int i=n; i>1; --i){int v = rnk[i], u = fa[v];f[0][u] += min(f[0][v], f[1][v] + k);f[1][u] += min(f[1][v], f[0][v]);} return min(f[0][1], f[1][1] + k);
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>str; int len = sqrt(n);for(int i=1, u, v; i<n; ++i){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);} dfs(1, 0);for(int i=1; i<=len; ++i) cout<<solve(i)<<'\n';int l = len + 1, r = n, ans = solve(len + 1), bg, del = ans - solve(len);do{bg = l;while(l < r){int mid = (l + r + 1) >> 1;if(solve(mid) - solve(mid - 1) < del) r = mid - 1;else l = mid;} bg = l - bg + 1;do{cout<<ans<<'\n';--bg; ans += del;} while(bg);l = l + 1, r = n, ans = solve(l), del = ans - solve(l - 1);} while(l <= n);return 0;
}

以后这种题暴力打完先找找规律再去想正解。

J [USACO23OPEN] Pareidolia P

8 pts 的 \(\mathcal{O}(N^3)\) 暴力还是很好打的。若想优化到 \(\mathcal{O}(N^2)\) 查询 \(\mathcal{O}(N)\) 需要用到 DP。令 \(f_{i,0\sim5}\) 表示所有以第 \(i\) 个字符为末尾的字符串中匹配到了 bessie 第 \(0\sim5\) 的位置的数量，类似于一个桶，很好写出 20 pts暴力。

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2e5 + 5;
string str;
int n, q, f[N][6];
inline int solve(){for(int i=1; i<=n; ++i) for(int j=0; j<6; ++j) f[i][j] = 0;int ans = 0, res = 0;for(int i=1; i<=n; ++i){for(int j=0; j<6; ++j) f[i][j] = f[i-1][j];switch(str[i]){case 'b': f[i][1] += f[i][0], f[i][0] = 0; break;case 'e': f[i][2] += f[i][1], f[i][1] = 0;res += f[i][5], f[i][0] += f[i][5], f[i][5] = 0; break;case 's': f[i][4] += f[i][3], f[i][3] = 0;f[i][3] += f[i][2], f[i][2] = 0; break;case 'i': f[i][5] += f[i][4], f[i][4] = 0; break;}++f[i][str[i] == 'b' ? 1 : 0];ans += res;} return ans;
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>str>>q; n = str.size(); str = ' ' + str;cout<<solve()<<'\n';while(q--){int x; char ch;cin>>x>>ch; str[x] = ch;cout<<solve()<<'\n';}
}

正解动态 DP。黑科技。就是线段树 + 矩阵乘法。把 DP 的递推过程转化为矩阵乘法，线段树每一个节点都是一个矩阵。唯一难点在于转移矩阵的设计。剩下的就是个绿。注意卡空卡时。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i) for(int i=0; i<9; ++i)
constexpr int N = 2e5 + 5;
string str; int n, q;
struct Matrix{ int m[9][9]; } bas;
Matrix operator * (const Matrix &a, const Matrix &b){Matrix c; memset(c.m, 0, sizeof(c.m));f(i) f(j) f(k) c.m[i][j] += a.m[i][k] * b.m[k][j];return c;
}
inline Matrix get(char ch){Matrix a; memset(a.m, 0, sizeof(a.m));f(i) a.m[i][i] = 1; a.m[1][0] = 1;switch(ch){case 'i': a.m[6][6] = 0, a.m[6][7] = 1; break;case 's': a.m[4][4] = a.m[5][5] = 0, a.m[4][5] = a.m[5][6] = 1; break;case 'b': a.m[2][2] = 0, a.m[2][3] = 1; break;case 'e': a.m[3][3] = a.m[7][7] = 0; a.m[7][0] = a.m[7][1] = a.m[7][2] = a.m[3][4] = 1; break;} a.m[8][ch == 'b' ? 3 : 2] = 1;return a;
}
namespace ST{#define ls (id << 1)#define rs (id << 1 | 1)Matrix t[N<<2];inline void pushup(int id){t[id] = t[ls] * t[rs];}inline void build(int id, int l, int r){if(l == r) return void(t[id] = get(str[l]));int mid = (l + r) >> 1;build(ls, l, mid), build(rs, mid+1, r);pushup(id);}inline void modify(int id, int l, int r, int pos){if(l == r) return void(t[id] = get(str[l]));int mid = (l + r) >> 1;if(pos <= mid) modify(ls, l, mid, pos);else modify(rs, mid+1, r, pos);pushup(id);}
}
inline int getans(){Matrix ans = bas * ST::t[1];return ans.m[0][0];
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>str>>q; n = str.size(); str = ' ' + str;bas.m[0][8] = 1;ST::build(1, 1, n); cout<<getans()<<'\n';while(q--){int x; char ch; cin>>x>>ch;str[x] = ch; ST::modify(1, 1, n, x);cout<<getans()<<'\n';} return 0;
}

K [USACO23OPEN] Good Bitstrings P

观察了一会儿性质，发现 \(S\) 每 \((a+b)/\gcd(a,b)\) 一个循环，感觉和 \(\gcd\) 有关，找了半天规律也没找出个啥。学习一下题解。

考虑将所有时刻的 \(ia,ib\) 作为坐标画到平面直角坐标系上，然后分析性质。

• 那么有射线 \((a,b)\)，如果某一点在 \((a,b)\) 下方，那么下一步一定是往上走的，如果在上方，那么下一步一定是往右走的。

  可以对题目代码的判断式进行移项：\(\frac{ia}{ib}\le\frac{a}{b}\) 往右走，反之往左走。

• 点 \((x,y)\) 合法当且仅当所有 \(0\le x'<x，0\le y' < y\) 的点都在射线 \((a,b)\) 和 \((x,y)\) 同侧。

  反证法证明：假设 \((a,b)\times (x,y)>0，k_{a,b}>k_{x,y}\)，点 \((x',y')\) 在异侧，那么对于射线 \((a,b)\)，这个点要往上走，而对于射线 \((x,y)\)，这个点要往右走，矛盾。

• 对于满足 \(f_1\times f_2=1\) 的整点 \(f_1,f_2\)，任意满足 \(f_1\times f > 0\) 并且 \(f\times f_2>0\) 的整点 \(f\) 都有 \(f=k_1f_1+k_2f_2\)。\(k_1,k_2\) 皆为正整数。

  怎么理解呢？就是任意整点（向量） \(f\) 都可以被分解为两个满足叉乘为 \(1\) 的整点（向量）之和。

  必要性证明：构造 \(k_2=f_1\times f, k_1=f\times f_2\)，于是有 \(f_1\times f=f_1 \times (k_1f_1+k_2f_2),f\times f_2=(k_1f_1+k_2f_2)\times f_2\)，从而 \(f=(f\times f_2)f_1+(f_1\times f)f_2\)。由于 \(f_1,f_2,f\) 均为整点，所以 \(k_1,k_2\) 均为正整数。又因为向量分解为两个非平行向量的分解方式唯一，所以必要性得证。

  有了这一条性质，就可以考虑递推求所有合法点：

  1. 初始令 \(f_1=(0,1),f_2=(1,0)\)，满足 \(f_1\times f_2=1\)，过程保证射线 \(f_1,f_2\) 之间的点都被统计过，并且 \(f_1,f_2\) 均为合法点。
  2. 记 \(f=f_1+f_2\)，则 \(f\) 为合法点。接下来按照 \(f\) 对于 \((a,b)\) 的位置决定令 \(f_1=f\) 或 \(f_2=f\) 继续向下递归。
  3. 若 \(f_2\times f=0\)，结束算法。

  但是这个算法漏统计了若干个形如 \(kf_2\) 的点，考虑完善一下。

• 若当前的 \(f\) 满足 \(f\times (a,b)>0\)，记在此之前 \(f_1\) 已经连续变化了 \(k\) 次，则 \((k+2)f_2\) 合法。

  到这里已经看不懂了……😵

• 算法结束时一定有 \(f_2=(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)})\)，且 \(f_1\times (a,b)=\gcd(a,b)\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T, a, b;
inline int solve(int a, int b){int f1 = b, f2 = a, ans = 0, co = 1;while(f2){if(f1 > f2) ans += co * ((f1 - 1) / f2), f1 = (f1 - 1) % f2 + 1;else ans += f2 / f1, f2 %= f1, co = 2;} return ans + 2 * (f1 - 1);
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>T; while(T--)cin>>a>>b, cout<<solve(a, b)<<'\n';return 0;
}

大坑待补。

L [USACO23OPEN] Triples of Cows P

黑的。