简单题还能写挂，感觉没救了啊 /fd /fd /fd题解由于保证每个点至少有一个出边，所以操作次数等于走的边数+1。由于这个步数可能到达 $\infty$，对于这种问题算期望的一种方法是：对于所有还没有停止的情况，算它们的概率的和。所以考虑一个暴力的 dp：设 $f_{i,j,k}$ 表示当前走了 $i$ 步（注意这里的步是指尝试加入了几次边，而不是走过的边数，最后答案减一即可），已经加入了 $j$ 条边，现在在点 $k$ 的概率。如果能预处理出 $h_i$ 表示 $n$ 个点 $i$ 条边的非连通图在所有 $i$ 条边的图中的概率，就可以用 $\sum_{i,j,k} f_{i,j,k} \times h_j$ 来统计答案了。但是这里 $i$ 没有限制，所以状态就是 $O(\infty)$ 的（先考虑如何转移：根据定义可以得到：$$ \begin{align} f_{0,0,1} &= 1\\ f_{i,j,k} &= \sum_{(v,k) \in E} (f_{i-1,j,v}\times (1-p_v) + f_{i-1,j-1,v} \times p_v) \times \frac{1}{out_v} \end{align} $$考虑尝试去掉第一维。设 $g_{i,j} = \sum_{x} f_{x,i,j}$，考虑如何对 $g_{i,j}$ 转移，显然有：$$ g_{i,j} = \sum_{(v,j) \in E} (g_{i,v} \times (1-p_v) + g_{i-1,v} \times p_v) \times \frac{1}{out_v} + [i = 0 \and j = 1] $$后面那个加号是为了修正 $f_{0,0,1}$ 的情况。直接高斯消元可以达到 $O(n^9)$ 的复杂度。一种经典优化是我们按照 $i$ 分类进行优化，我们处理到 $i$ 的时候一定已经知道了 $g_{i-1,*}$ 的值，所以每一次消元只有 $O(n)$ 个变量，直接做复杂度是 $O(n^5)$ 的。高斯消元实际上是求解 $Ax = b$，不难发现每次变化的只有 $b$，所以我们预处理 $A^{-1}$，每次就可以 $O(n^2)$ 直接求出 $x = A^{-1}b$ 了，复杂度 $O(n^4)$。现在考虑如何计算那个 $h$。这其实就是前几天的模拟。设 $f_{i,j}$ 表示 $i$ 个点 $j$ 条边的无向连通图个数，显然 $h_i = \binom{\binom n 2}{i} - f_{n,i}$。暴力转移：$$ f_{i,j} = \binom{\binom n 2}{i} - \sum_{k=1}^{i-1} \binom{i-1}{k-1} \sum_{x=0}^{j} f_{k,x} \binom{\binom{i-k}{2}}{j-x} $$考虑写成 Poly 的形式：设 $F_i$ 是 $f_{i,j}$ 的生成函数，转移可以写成：$$ F_i = (1+x)^{\binom n 2} - \sum_{k=1}^{i-1} \binom{i-1}{k-1} F_k \times (1+x)^{\binom {i-k}{2}} $$将 $F$ 看成关于 $(1+x)$ 的函数，需要转移 $O(n)$ 次，每次要进行 $n$ 次多项式平移，复杂度 $O(n^4)$。最后手动展开 $(1+x)^i$ 就好了。写一下我怎么写挂的：入度出度写反了，转移的时候拿的 $out_k$ 而不是 $out_v$，输了两次，双输！代码#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 100 + 5; const int MAXM = 1e5 + 5; const int ha = 1e9 + 7; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n&1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } int n,m; int p[MAXN]; int fac[MAXM],inv[MAXM]; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } inline int C(int n,int m){ return n < 0 || m < 0 || n < m ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha; } std::vector<int> G[MAXN];// in edge int f[MAXN][MAXN*MAXN];// sum aj(x+1)^j int g[MAXN*MAXN];// i edge, unconnected int A[MAXN][MAXN],B[MAXN][MAXN],vec[MAXN],b[MAXN]; int invm[MAXN]; inline void Inv(){ FOR(i,1,n) B[i][i] = 1; FOR(i,1,n){ int ps = -1; FOR(j,i,n) if(A[j][i]){ps = j;break;} if(ps != i) std::swap(A[ps],A[i]),std::swap(B[ps],B[i]); int inv = qpow(A[i][i]); FOR(j,1,n) A[i][j] = 1ll*A[i][j]*inv%ha,B[i][j] = 1ll*B[i][j]*inv%ha; FOR(j,1,n){ if(j == i) continue; int d = A[j][i]; FOR(k,1,n){ add(A[j][k],ha-1ll*A[i][k]*d%ha); add(B[j][k],ha-1ll*B[i][k]*d%ha); } } } } int main(){ fac[0] = 1;FOR(i,1,MAXM-1) fac[i] = 1ll*fac[i-1]*i%ha; inv[MAXM-1] = qpow(fac[MAXM-1]);ROF(i,MAXM-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha; scanf("%d%d",&n,&m);int i100 = qpow(100); FOR(i,1,n) scanf("%d",p+i),p[i] = 1ll*p[i]*i100%ha; FOR(i,1,m){ int u,v;scanf("%d%d",&u,&v); G[v].pb(u);++invm[u]; } f[1][0] = 1; FOR(i,2,n){ f[i][i*(i-1)/2] = 1; FOR(j,1,i-1){ int c = C(i-1,j-1),off = (i-j)*(i-j-1)/2; FOR(k,off,i*i) add(f[i][k],ha-1ll*f[j][k-off]*c%ha); } } FOR(i,1,n) invm[i] = qpow(invm[i]); FOR(i,0,n*(n-1)/2) g[i] = C(n*(n-1)/2,i); FOR(i,0,n*(n-1)/2){ int c = 0; FOR(j,i,n*(n-1)/2) add(c,1ll*f[n][j]*C(j,i)%ha); add(g[i],ha-c); g[i] = 1ll*g[i]*qpow(C(n*(n-1)/2,i))%ha; } FOR(i,1,n){ for(auto x:G[i]) add(A[i][x],1ll*(1-p[x]+ha)%ha*invm[x]%ha); add(A[i][i],ha-1); } Inv(); int ans = 0; FOR(i,0,n*(n-1)/2){ FOR(v,1,n){ b[v] = 0; for(auto x:G[v]) add(b[v],1ll*vec[x]*p[x]%ha*invm[x]%ha); b[v] = 1ll*b[v]; if(i == 0 && v == 1) add(b[v],1); b[v] = (ha-b[v])%ha; } FOR(j,1,n){ vec[j] = 0; FOR(k,1,n) add(vec[j],1ll*B[j][k]*b[k]%ha); } int sm = 0; FOR(j,1,n) add(sm,vec[j]); add(ans,1ll*sm*g[i]%ha); } add(ans,ha-1); printf("%d\n",ans); return 0; }
题意问有多少个 $n$ 个点的完全图，满足所有边权在 $[1,K]$ 内，并且最小生成树只有一个。答案对质数 $p$ 取模。$n \leq 50,K \leq 10^9,\max(n,K)+1 \leq p \leq 10^9$。题解先考虑如何求最小生成树：将所有边从小到大排序，按照顺序选择两个端点不在一个联通块的边，并合并这两个联通块。所以我们可以考虑按照权值去考虑这些边：设 $f_{n,k}$ 表示考虑有 $n$ 个点的完全图，唯一的最小生成树的边权都 $\leq k$ 的方案数。考虑如何转移：假设树上有边权为 $k$ 的边，我们删去这些在最小生成树上边权为 $k$ 的边，发现这个树一定分成了若干个联通块。联通块之间的边边权一定要 $>k$ 否则方案不唯一；然后就分解成了若干个子问题。发现这个方案数和权值都和每个联通块的大小有关，所以我们考虑去做计数。先考虑一个暴力是枚举联通块的大小。为了防止计算重复，我们按顺序枚举：先枚举 $1$ 号点所在的联通块大小 $s_1$，再枚举剩下的点中最小权值的点所在的联通块大小 $s_2,s_3,\ldots,s_m$，这样可以得到选点方案数就是 $\binom{n-1}{s_1-1}\binom{n-s_1-1}{s_2-1}\ldots$。接下来我们要计算生成树个数，这个题相当于就是每有一条连向大小为 $x$ 的块的边，对答案贡献就要乘上一个 $x$，根据经典的结论可以得到这样的方案数是 $(\sum s_i)^{m-2} \prod s_i = n^{m-2} \prod s_i$。然后需要决定剩下的边的权值，每个都可以填 $(k,K]$ 中的任何一个数字，方案数是 $(K-k)^{\binom n 2 - \sum_{i=1}^m \binom {s_i}{2} - (m-1)}$。把这些东西乘起来就是这一个枚举对答案的贡献。但是直接暴力显然不可行，我们考虑如何优化转移。这种优化显然是写成每次加入一个大小为 $x$ 的块，乘上的系数是和 $x$ 有强相关的式子的形式，所以可以写成：$$ n^{-2}(K-k)^{\binom n 2 +1}\sum_{s_1,s_2,\ldots,s_m} \prod_{i=1}^m \binom{n-\sum_{j=1}^{i-1} s_j - 1}{s_i-1} s_i n (K-k)^{-(\binom {s_i} 2 + 1)} f_{s_i,k-1} $$发现系数只需要知道之前的 $\sum s_i$ 就好了。这样每次转移可以再跑一个 dp：设 $g_i$ 表示已经 $\sum s_i = i$ 的系数和，转移枚举当前的联通块长度，乘上对应的权值即可。也就是$$ g_i = \sum_{j=1}^i g_{i-j} \binom{n-(i-j)-1}{j-1} j n (K-k)^{-(\binom j 2 +1)} f_{j,k-1} $$然后最后乘上外面那一堆东西就好了。复杂度 $O(n^3K)$。这题 $K$ 很大，所以我们会去思考是否可以插值。打表发现 $f_n$ 关于 $k$ 是一个 $O(n^2)$ 项多项式，所以 $O(n^5)$ 求出点值然后写个插值就过了。需要稍微卡下常数，因为 tc 的机子并不快。。。证明：设 $f_i$ 的次数是 $d_i$，根据最初的暴力式子可以得到：$$ \begin{aligned} d_n &= \binom n 2 + 1 + \sum_i (d_{s_i}-\binom {s_i} 2 -1)\\ &= O(n^2) - \sum_i d_{s_i}-O(s_i^2) \end{aligned} $$所以取 $d_i = O(i^2)$ 大概就能放过去。代码（代码内附赠一组我一开始跑的很慢的数据）#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 50 + 5; const int MAXM = 2500 + 5; int ha; class UniqueMST{ private: int f[MAXN][MAXM]; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } // i 个点,j 个颜色 int tmp[MAXN]; int pw[MAXM]; int C[MAXN][MAXN]; int fac[MAXM],inv[MAXM]; int pre[MAXM],suf[MAXM]; inline int cha(int f[],int n,int x){ pre[0] = suf[n+1] = 1; FOR(i,1,n) pre[i] = 1ll*pre[i-1]*(x-i+ha)%ha; ROF(i,n,1) suf[i] = 1ll*suf[i+1]*(x-i+ha)%ha; int ans = 0; FOR(i,1,n){ int c = 1ll*pre[i-1]*suf[i+1]%ha*inv[i-1]%ha*inv[n-i]%ha*f[i]%ha; if((n-i)&1) c = (ha-c)%ha; add(ans,c); } return ans; } public: int count(int N,int K,int m){ ha = m; if(N == 2) return K%ha; int lim = std::min(MAXM-1,m-1); fac[0] = 1;FOR(i,1,lim) fac[i] = 1ll*fac[i-1]*i%ha; inv[lim] = qpow(fac[lim]);ROF(i,lim-1,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha; C[0][0] = 1; FOR(i,1,MAXN-1){ C[i][0] = 1; FOR(j,1,i) C[i][j] = (C[i-1][j]+C[i-1][j-1])%ha; } FOR(k,1,std::min(K,N*N)) f[1][k] = 1,f[2][k] = k;f[1][0] = 1; // 特判 k == K: [n==2] 种 FOR(n,3,N){ int invn2 = 1ll*inv[n]*fac[n-1]%ha; invn2 = 1ll*invn2*invn2%ha; FOR(k,1,std::min(K,N*N)){ int inv = qpow(K-k);CLR(tmp,0); pw[0] = 1;FOR(i,1,n) pw[i] = qpow(inv,i*(i-1)/2+1); tmp[0] = 1; FOR(i,1,n){ LL s = 0; FOR(j,1,i){ s += 1ll*tmp[i-j]*j%ha*n%ha*f[j][k-1]%ha*pw[j]%ha*C[n-(i-j)-1][j-1]%ha; } tmp[i] = s%ha; } add(f[n][k],1ll*tmp[n]*qpow(K-k,n*(n-1)/2 + 1)%ha*invn2%ha); } } if(K <= N*N) return f[N][K-1]; return cha(f[N],N*N,K); } }; #ifdef RainAir int main(){ printf("%d\n",(new UniqueMST)->count(48,255871602,923853737)); return 0; } #endif
题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2),(a_2,a_3),\ldots,(a_{m-1},a_m)$ 之间也会有一条双向铁路。现在已经确定了某些村庄的分配情况，需要求出有多少种分配剩下的村庄的方案，使得从 $0$ 到 $n$ 的最短路 $\leq k$ 。每条铁路经过的时间都为 $1$。对 $10^9+7$ 取模。$n \leq 4000$题解神仙题。。。启发：很多转移带环的最短路问题，如果最后有要求按照某个顺序 dp 的话，可以考虑这个环会影响哪些情况，有时候可以「假设」满足这些情况，然后发现在假设不成立的时候这个限制是更松的，就可以对了。还是按照套路，先考虑如何判定某个状态是否合法：我们就从 $0$ 开始按照边跑一个 bfs，判断一下 $n$ 位置的最短路是否 $\leq k$ 就好了。所以如果想计数的话，应该是把这个最短路过程压入 dp 状态。直接暴力记录所有点的 $dis_v$ 数组显然不可以，所以我们考虑一下这个图的最短路有没有什么特别之处。这个题由于是无向边，最短路需要考虑如何处理往回走的情况。发现往回走到达某个点是最短路，当且仅当它在一大块和它一样的字母中，这样先跳到后面的那个字母，再倒着走回来。也就是说，倒着走是这种情况：这样会比正着走可能要快一点。其实就是相当于花费了 $2$ 的代价，可以倒着遍历。也就是说，我们每次扩展一个新的字符，如果这个字符的最短路最后一步是从右边过来的，那么一定是从它右边的第一个和它不一样的位置过来的（中间可能经过多个一样的位置）。还是以 $i$ 位置的 A 举例，首先如果倒着走，一定是有一次从 $i$ 的前面跑到 $i$ 的后面了，而 A 显然不可能跨过中间的 A 直接到后面的 A，所以只有可能是从 $i$ 前面的 B 跳到了后面，然后后面这个 B 到 $i$ 这一段一定全是 A（因为恰好是下一个 B），所以只能一步步倒回去。所以也不会多次跨过 A（因为无论如何都在 A 后面第一个 B 停下）。联想到在结束的时候最后一个位置一定同时是 A 和 B，所以我们在考虑一段的时候可以假设这一段后面就是和它不一样的一个字母（也就是支持倒着走）。设 $f_{i,j,k,0/1}$ 表示考虑了前 $i$ 个位置，当前位置的最短路是 $j$，和当前位置不同的字母最靠后的位置的最短路是 $k$，当前位置的字母是 A/B，假设下一个字母和当前位置的字母不同的方案数。转移我们以要填 A 为例。如果 $i+1$ 位置是 A，$i$ 位置是 B：那么还是维持之前的假设的，所以 $j,k$ 这两个最短路可以直接拿过来用，转移就考虑从 B 走过来（$k+1$）还是从上一个 A 走过来（$j+1$）就好了。如果 $i+1$ 位置是 A，$i$ 位置也是 A：这时候就破坏了之前的假设，考虑是否能 fix。如果想从上一个 B 转移过来，看起来是不影响的，因为我们接下来要假设 $i+1$ 后面一个位置是不同的，所以用 $k+2$ 更新；如果想从上一个 A 转移过来，要讨论一下：如果上一个 $A$ 的最短路没有通过假设的 $B$ 走过来的，说明这个最短路还是对的，用 $j+1$ 更新；如果上一个 $A$ 的最短路是倒着从假想的 $B$ 走过来的，如果我们用 $j+1$ 更新，肯定会比 $k+2$ 大（因为这实际上是用 $k+3$ 更新：上一次这个 $j$ 是用 $k+2$ 更新，这次又要 $+1$），所以这个问题不用担心对于填 B 是类似的。复杂度 $O(n^3)$。优化的话，考虑在这个假设下，$|j-k| \leq 2$（因为可以花最多 $2$ 步相互到达），所以就可以优化到 $O(n^2)$ 了。代码#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 4000 + 5; const int ha = 1e9 + 7; const int off = 2; int n,k; char str[MAXN]; int f[2][MAXN][5][2],now; // [-2,2] inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int main(){ scanf("%d%d",&n,&k); scanf("%s",str+1); CLR(f[now=0],0); if(str[1] != 'B') f[now][1][-1+off][0] = 1; if(str[1] != 'A') f[now][0][1+off][1] = 1; FOR(i,2,n-1){ CLR(f[now^1],0); FOR(j,0,n){ FOR(k,-2,2){ int c0 = f[now][j][k+off][0],c1 = f[now][j][k+off][1]; if(!c0 && !c1) continue; int d0 = j,d1 = j+k; if(str[i] != 'B'){ int dis = std::min(d0+1,d1+2); add(f[now^1][dis][d1-dis+off][0],c0); dis = std::min(d0+1,d1+1); add(f[now^1][dis][d1-dis+off][0],c1); } if(str[i] != 'A'){ int dis = std::min(d0+1,d1+1); add(f[now^1][d0][dis-d0+off][1],c0); dis = std::min(d0+2,d1+1); add(f[now^1][d0][dis-d0+off][1],c1); } } } now ^= 1; } int ans = 0; FOR(i,0,n){ FOR(j,-2,2){ int da = i,db = i+j; if(da >= k && db >= k) continue; FOR(k,0,1){ add(ans,f[now][i][j+off][k]); } } } printf("%d\n",ans); return 0; }
A先将其压成二进制数，考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数，也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下，发现两个数不同，当且仅当一个是 $1$ 一个是 $0$，我们只考虑这些不同的位置，发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ 和偶数个 $1$ 的数量，乘起来就好了。B$C_{i,j} = A_i + B_j$。我们考虑第 $i$ 行，就是 $B$ 序列整体加上了一个 $A_i$，于是差分一下就可以算出 $B$ 序列的差分序列。考虑列也可以算出 $A$ 序列的差分序列。首先如果通过不同的行/列算出的差分序列不同一定是无解的。现在关键在于决定 $A_1,B_1$ 是啥，知道这个之后就可以推出来了。首先我们有 $A_1+B_1 = C_{1,1}$，然后由于这个题要求非负整数，根据差分数组的前缀和的最小值，我们还有两个限制 $A_1 \geq l_1,B_1 \geq l_2$。随便找出一组可行解那么它一定满足限制。C我们考虑估一个答案的下界：$\lfloor \log_2 n \rfloor$。因为所有形如 $2^x$ 的数字组成了一个团。那么我们考虑如何构造能让如果 $x|y$，那么 $a_x \neq a_y$：可以想到如果 $x$ 整除 $y$，那么 $x$ 唯一分解后 $\sum e_i$ 一定是小于 $y$ 的，所以我们构造这个序列即可。注意特判 $1$，所以其实整体都是要加一的，那个下界也应该是 $\lfloor \log_2 n \rfloor + 1$。另一种做法：考虑将 $n$ 的因数分解为若干组，每一组满足两两都是除数/被除数的关系。每一组都是一个团，所以我们只需要找到这些团的最大值然后加一就好了。简化一下：也就是找到所有因数的答案的最大值加一就好了。D欧拉回路有一个经典的结论：求出一个 dfs 树后等价于 dfs 树上若干个树环（只包含一个非树边）的异或。但是这个题需要求有 $k$ 个奇点的数量怎么办？我们求欧拉回路的时候如果有奇点一般的处理方法都是建立一个新点，连所有奇点。由于奇点一定有偶数个，所以连完之后一定变成一个欧拉图。我们考虑用类似的方法计数：首先肯定要分联通块考虑，设一个 $n$ 个点 $m$ 条边的联通块，选出恰好 $k$ 个奇度点（$k$ 是偶数）的方案是：首先我们要选出这 $k$ 个点向新点连边，这一部分方案是 $\binom{n}{k}$；然后我们要选一些新图上的树环，但是注意：由于我们钦定了奇度点，所以我们必须选择连接之后新产生的环，而原先的环的数量显然是 $m-n+1$。所以答案就是 $\binom n k 2^{m-n+1}$。多个联通块卷起来就好了。复杂度 $O(n^2)$。可以用分治+NTT之类技巧优化到 $O(n \log^2 n)$ 但是没必要。E考虑容斥。我们枚举把它划分成 $t$ 个段，每段内都要相同，那么每段内可以取的数字就是从 $1$ 到这一段的最小值，对答案的贡献是 $(-1)^{n-t}$。我们可以把 $(-1)^{n-t}$ 看成 $(-1)^n \times (-1)^t$，然后 dp：设 $f_i$ 表示当前划分了前 $i$ 个数，并且 $i$ 是最后一段的结尾的答案。转移枚举这一段的开头是啥：$$ f_i = -\sum_{j=1}^i f_{j-1} \times \min(a_{j},a_{j+1},\ldots,a_{i}) $$这样直接做是 $O(n^2)$ 的。考虑优化：这个 min 让我们想到用单调栈维护。我们维护一个递增的单调栈 $b_1,b_2,\ldots,b_m$，这里的 $b_i$ 表示在原序列的位置。不难发现在 $[b_i,b_{i+1})$ 的 $j$，都满足 $\min(a_j,a_{j+1},\ldots,a_i)$ 是 $a_{b_i}$。所以我们对于栈内的位置 $i$，维护一下 $sm_i = \sum_{k=b_i}^{b_{i+1}-1} f_{k-1}$，再维护一个整体的和 $now = \sum_{i=1}^m b_ism_i$ 即可。弹栈的时候相当于合并区间，更新一下即可。复杂度 $O(n)$。F比较神仙。。。考虑一个最显然的暴力：将第 $i$ 个点当前在哪里看成一个 $k$ 元组，每个这样的 $k$ 元组看成一个新图点，权值是所有点的和；新图中的两个点有连边当且仅当它们可以一步到达。问从 $S$ 到 $T$ 的最小瓶颈路。看到最大值最小我们会去思考二分：设二分了一个上界 $L$，我们现在只需要保留所有权值 $\leq L$ 的状态，检查 $S,T$ 是否连通即可。由于状态之间的边都是无向边，所以我们考虑转而能否让它们都走到一个确定的状态：不妨让它们都走到能到达的状态的最小值，然后判断是否是同一个点即可。如果和相同就按照编号手动标号。那么我们跳出二分看一下这个过程：相当于是有 $k$ 个球位置集合为 $\{s_i\}$ 和另外 $k$ 个球 $\{t_i\}$，每次你可以选择一个点走到一个 $h_i$ 比它小的点，走到它们完全相同位置。我们对于原图每个点预处理出所有 $h_i$ 比它小的点中代价最少的（就是路径上最大值最小的），然后每次将一个球移动到它所在的点预处理出的位置，更新一下答案。贪心选最小贡献，一直走到相同为止。走过的路径就是答案。因为这个在二分的基础上每次保证了扩大了尽量小的上界，所以这个东西求出的方案和原问题是等价的。复杂度 $O(n^2 \log n)$。
A把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 200+5; char str[MAXN]; int cnt[26],n; int main(){ int T;scanf("%d",&T); while(T--){ CLR(cnt,0);scanf("%d",&n); scanf("%s",str+1); FOR(i,1,n) ++cnt[str[i]-'a']; FOR(i,1,cnt[1]) putchar('b'); FOR(i,0,25){ if(i == 1) continue; FOR(j,1,cnt[i]) putchar('a'+i); } puts(""); } return 0; }B我们证明答案一定 $\leq 1$：假设答案 $\geq 2$，考虑最后一步和倒数第二步，倒数第二步会把最后一步操作的点直接拉过来，所以最后一步的操作是无效的，可以删去。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 100+5; int n,x[MAXN],y[MAXN],k; inline void Solve(){ scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d%d",x+i,y+i); FOR(i,1,n){ int mx = 0; FOR(j,1,n) mx = std::max(mx,std::abs(x[i]-x[j])+std::abs(y[i]-y[j])); if(mx <= k){ puts("1"); return; } } puts("-1"); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }C1感觉比较难。。发现三个相邻的点 $i+j \bmod 3$ 两两不同，于是按照 $i+j \bmod 3$ 分类，找一个最小的将其全部翻转即可。C2会了 C1 稍微想想就会了。我们现在把 X 分成三类 $x_0,x_1,x_2$，把 O 分成三类 $o_1,o_2,o_3$，显然我们只需要选一对 $p \neq q$，将 $x_p$ 全都变为 O，并且将 $x_q$ 全都变为 X，可以得到这样是 $\leq \frac{1}{3}$ 的。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 300+5; char str[MAXN][MAXN];int n; int mp[MAXN][MAXN]; int cnt[2][3],ps[2]; inline void Solve(){ scanf("%d",&n);CLR(cnt,0); FOR(i,1,n){ scanf("%s",str[i]+1); FOR(j,1,n){ if(str[i][j] != '.') ++cnt[str[i][j]=='X'][(i+j)%3]; } } ps[0] = ps[1] = -1; int mn = 1e9; FOR(i,0,2){ FOR(j,0,2){ if(i == j) continue; if(mn > cnt[0][i]+cnt[1][j]){ mn = cnt[0][i] + cnt[1][j]; ps[0] = i;ps[1] = j; } } } FOR(i,1,n){ FOR(j,1,n){ if(str[i][j] == '.') putchar(str[i][j]); else{ if(str[i][j] == 'O') putchar((i+j)%3 == ps[0] ? 'X' : 'O'); else putchar((i+j)%3 == ps[1] ? 'O' : 'X'); } } puts(""); } } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }D特判 $k=1$ 和 $k=n$。考虑 $k \in [2,n-1]$ 的情况：首先最小值 $1$ 肯定要出现且仅出现一次，发现只需要出现一次的位置一定是边界，所以等价于要判断是否只有一个 $1$ 并且这个 $1$ 在边界上，然后删掉这个 $1$ 变成了一个子问题。我们就可以求出最长能凑出多少的排列了。感觉比 C 简单。。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; int n,a[MAXN]; bool vis[MAXN]; bool f[MAXN]; int cnt[MAXN]; inline void Solve(){ scanf("%d",&n);FOR(i,1,n) cnt[i] = 0; FOR(i,1,n) scanf("%d",a+i),vis[i] = 0,++cnt[a[i]]; FOR(i,1,n) vis[a[i]] = 1,f[i] = 0;f[0] = 1; int sm = 0; FOR(i,1,n) f[i] = f[i-1]&vis[i],sm += vis[i]; std::reverse(f+1,f+n+1); int l = 1,r = n,now = 1; while(l <= r){ if(a[l] != now && a[r] != now) break; --cnt[now]; if(cnt[now]) break; if(a[l] == now) ++l,++now; else if(a[r] == now) --r,++now; } --now; FOR(i,1,n-now-1) f[i] = 0; if(sm == n) f[1] = 1; if(vis[1]) f[n] = 1; FOR(i,1,n) putchar('0'+f[i]);puts(""); } int main(){ int T;scanf("%d",&T);while(T--) Solve(); return 0; }E其实是个差分约束题（首先相邻两个人一定奇偶性不同，所以如果不是二分图直接无解。考虑一条无向边 $(u,v)$，相当于有限制 $|a_u-a_v| = 1$，不妨先写成 $|a_u-a_v| \leq 1$；考虑一条有向边 $u \to v$，相当于有限制 $a_v-a_u=1$，也就是 $a_v-a_u \leq 1$ 和 $a_v-a_u \geq 1$。我们按照上面不等式建差分约束然后跑最短路，枚举一个起点，求出距离起点最远的距离，显然这个距离的最大值就是答案。首先答案一定不能超过这个值，所以我们只要构造出一组合法的解就好了。我们取能取到最大值的起点，将点 $i$ 的权值直接设为起点到 $i$ 的最短路就好了。因为这是一个二分图，所以无向边的情况不可能有 $a_u=a_v$（因为都是连的 $1$ 边，如果有这个情况说明一定不是二分图了）。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 200+5; int G[MAXN][MAXN],dis[MAXN][MAXN]; int n,m; bool flag=1; int col[MAXN]; bool vis[MAXN]; inline void dfs(int v){ vis[v] = 1; FOR(i,1,n){ if(G[v][i] == 1e8 || v == i) continue; if(vis[i]) flag &= (col[v]^col[i]); else col[i] = col[v]^1,dfs(i); } } int main(){ scanf("%d%d",&n,&m); FOR(i,1,n) FOR(j,1,n) G[i][j] = 1e8; FOR(i,1,n) G[i][i] = 0; while(m--){ int i,j,w;scanf("%d%d%d",&j,&i,&w); if(!w){ G[j][i] = std::min(G[j][i],1); G[i][j] = std::min(G[i][j],1); } else{ G[j][i] = std::min(G[j][i],1); G[i][j] = std::min(G[i][j],-1); } } dfs(1); if(!flag){ puts("NO"); return 0; } FOR(i,1,n) FOR(j,1,n) dis[i][j] = G[i][j]; int cir = 1e9; FOR(k,1,n){ FOR(i,1,k-1){ FOR(j,1,k-1){ if(i == j) continue; cir = std::min(cir,G[k][i]+G[j][k]+dis[i][j]); } } FOR(i,1,n){ FOR(j,1,n){ dis[i][j] = std::min(dis[i][j],dis[i][k]+dis[k][j]); } } } // FOR(i,1,n) FOR(j,1,n) if(G[i][j] != 1e9 && i != j) printf("%d %d %d\n",i,j,G[i][j]); if(cir < 0){ puts("NO"); return 0; } int mx = 0,ps = -1; FOR(i,1,n){ int c = -1e9; FOR(j,1,n) c = std::max(c,dis[i][j]); if(mx < c){ mx = c;ps = i; } } puts("YES"); printf("%d\n",mx); FOR(i,1,n) printf("%d%c",dis[ps][i]," \n"[i==n]); return 0; }F还是结论题，完全不会这个操作实际上就是将原排列分成尽量少的段，将这些段翻转和重排后要求相邻的值不能相同。那么我们先考虑如何判断对于一个分成了 $k+1$ 段的切割方案，是否存在一种操作方案，能重排后相邻值不相同。首先我们要保证每段内部不能有相邻相同的对，因为操作影响不到内部的点。设 $f(c)$ 表示颜色 $c$ 在端点上的出现次数，一个显然的限制是 $f(c) \leq k+2$，我们现在说明只要满足这个限制的所有切割方案都是合法的：考虑对 $k$ 归纳，如果 $k=0$ 时只有一段，命题显然成立；对于 $k \geq 1$ 的部分，考虑取最大值的 $f(x)$，找出一端是颜色 $x$ 的段，再随便找一个一端是颜色 $y(y \neq x)$ 的段，将 $x,y$ 对着拼在一起，现在相当于是一个 $k-1$ 的局面，我们发现 $f(x)-1 \leq k-1+2$，$f(z) \leq k-1 \leq k$（因为如果非最大值 $> k$ 那么和就超过 $k+2$ 了），所以这个局面是合法的，归纳得证。所以我们先将所有相邻相同的地方都分开，然后看下是否满足条件，如果满足条件直接输出 $k$，否则我们要多切出一些段来让其满足条件。设最大值为 $f(x)$，分类讨论一下发现每次切开的两边的颜色都不能是 $x$，切到满足条件为止就好了。如果全都切完了还不满足条件就无解。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int n,a[MAXN],f[MAXN]; inline void Solve(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i),f[i] = 0; int k = 0; ++f[a[1]];++f[a[n]]; FOR(i,2,n){ if(a[i] == a[i-1]){ ++k;++f[a[i]];++f[a[i-1]]; } } int mx = 0,ps = -1; FOR(i,1,n){ if(mx < f[i]-k-2){ mx = f[i]-k-2; ps = i; } } if(!mx){ printf("%d\n",k); return; } int r = 0; FOR(i,2,n) if(a[i] != a[i-1] && a[i] != ps && a[i-1] != ps) ++r; if(mx <= r){ printf("%d\n",k+mx); } else{ puts("-1"); } } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }G先咕了，等个谁写个中文题解 （H1先考虑如何求 $f(c)$：首先发现如果有相邻相同颜色的点可以都删掉，于是我们只需要考虑黑白交替的 $f(c)$ 答案是啥：不难发现是黑色点数量除二。所以我们可以用栈来搞这个东西：每次加入一个新球，如果栈顶和这个球颜色相同就一块弹出栈，否则弹出栈并让答案 $+1$。不妨考虑哪些黑色点对答案有贡献：我们如果假设第一个点是黑色点的话，第一个点有贡献当且仅当下一个黑色点也是奇数位置的点（说明有一个白色和它配对掉了），如果下一个黑色点是偶数位置的话说明它和上一个黑色点消去了，设奇数位置，偶数位置黑色点数量为 $B_1,B_2$，白色为 $W_1,W_2$，答案就是$\frac{1}{2}|B_1-B_2|$。如果枚举 $B_1,B_2$ 然后计数很麻烦，考虑 $B_2+W_2=\frac{n}{2}$，所以这个式子可以换成 $\frac{1}{2}|B_1-\frac{n}{2}+W_2|$，我们枚举 $i=B_1+W_2$，设空位置数量为 $p$ ，已经有的 $b_1+w_2=c$，方案数就是 $\binom p {i-c}$，所以答案就是：$$ \frac{1}{2^p}\sum_{i=0,i \equiv \frac{n}{2} \pmod 2}^n \binom p {i-c} |i-\frac{n}{2}| $$我们改为枚举 $i-c$，设 $d=c-\frac{n}{2}$式子化简为：$$ \frac{1}{2^p}\sum_{i=0,i \equiv d \pmod 2}^n \binom p i |i-d| $$#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int ha = 998244353; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int fac[MAXN],inv[MAXN]; inline void prework(){ fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha; inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha; } inline int C(int n,int m){ return (n < 0 || m < 0 || n < m) ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha; } char str[MAXN]; int n,m; int main(){ prework(); scanf("%d%d",&n,&m); scanf("%s",str+1); int B1=0,W2=0,p=0; FOR(i,1,n){ B1 += (str[i] == 'b' && (i&1)); W2 += (str[i] == 'w' && (!(i&1))); p += (str[i] == '?'); } int ans = 0; FOR(x,0,n){ int c = C(p,x),d = std::abs(x-(n/2)+B1+W2); if(d&1) continue; c = 1ll*c*d%ha; add(ans,c); } ans = 1ll*ans*qpow(qpow(2,p))%ha; printf("%d\n",ans); return 0; }H2首先要解决 $i \equiv d \pmod 2$ 的限制的问题，发现 $\binom n m = \binom {n-1}{m}+\binom{n-1}{m-1}$，所以我们将式子写开，就去掉了这个限制。现在我们考虑如何维护如下式子的值：$$ \begin{aligned} \sum_{i=0}^n \binom p i |i-d| = \sum_{i=0}^d \binom p i d-\sum_{i=0}^d \binom p i i+\sum_{i=d+1}^n \binom p i i - \sum_{i=d+1}^n \binom p i d \end{aligned} $$发现 $\binom n m m= \binom {n-1}{m-1}n$，区间求和可以拆成前缀和询问，所以我们相当于要快速维护$$ \sum_{i=0}^{lim} \binom p i $$我们发现 $lim$ 和 $i$ 的变化都是 $O(1)$ 的，所以我们只需要考虑 $lim,p$ 加减 $1$ 的变化即可。$lim$ 加一直接加上对应的项即可。$\binom {p+1}{i} = \binom p i + \binom p {i-1}$，所以 $p$ 加一只需要额外维护一下 $0\ldots lim-1$ 的求和即可。注意特判 $p=1$ 的边界。代码咕了。
E题意有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的期望。限制所有都要完成一般都不好做，考虑 $min-max$ 容斥变成枚举一个集合 $S$ ，求 $\min_{i \in S} t_i$ 的期望。枚举集合后，问题变成求存在 $S$ 内某一个元素被随机 $b_i$ 次这个事件发生的期望时间。我们发现这样还是有可能随机到 $S$ 外的元素的，一个经典套路是算出期望多少次能操作一次 $S$ 内的元素，然后转化为只考虑 $S$ 内元素操作的问题，最后乘上去即可。可以发现这个期望次数为 $\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i}$。现在问题在于给定一个集合 $S$ ，在 $S$ 内随机，求存在一个数满足条件的期望时间。首先根据：$$ \sum_{i \geq 0} P[X=i]i = \sum_{i \geq 0} P[X \geq i] $$可以得到，我们只需要对于每个时间 $T$ 求出在 $T$ 时间还没结束的概率，求和即可。我们考虑如何暴力的计算：先枚举在时间 $T$ 结束，接下来枚举序列 $b_i$ 表示集合中元素 $i$ 被随机到的次数，需要满足 $\forall i \in S,b_i < B_i$，$\sum_{i \in S} b_i = T$，这样一个序列的概率就是 $\prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!}$。所以答案是：$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1}\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!} $$稍加整理可得$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1} \frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} T!(\frac{1}{\sum_{i \in S} A_i})^T \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in S} \frac{A_i^{b_i}}{b_i!} $$于是可以考虑对这个 dp：发现最终答案系数只和 $\sum b_i,\sum A_i$ 有关，我们带着容斥系数 dp，设 $f_{i,j,k}$ 表示考虑前 $i$ 个数，$\sum b_i = j,\sum A_i = k$ 的答案，转移的时候枚举这个位置选或者不选，选的话枚举 $b_i$ 是多少，可以得到转移式子：$$ f_{i,j,k} = f_{i-1,j,k}-\sum_{x=0}^{B_i-1}\frac{A_i^x}{x!} f_{i-1,j-A_i,k-x} $$然后最后把应该乘的系数乘上去就好了。假设 $n,\sum A,\sum B$ 同阶，看起来时间复杂度是 $O(n^4)$ 的，但是实际分析一下：复杂度是：$$ \begin{aligned} \sum_{i=1}^n \sum_{j=0}^{\sum A_i} \sum_{k=0}^{\sum B_i } \sum_{l=0}^{B_i-1} 1 &= \sum_{i=1}^n \sum_{l=0}^{B_i-1} (\sum A_i) (\sum B_i)\\ &=(\sum A_i)(\sum B_i)^2 \\ &= O(n^3) \end{aligned} $$所以可以通过此题。代码可能和博客定义的是反的，感性理解一下（#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 400+5; const int ha = 998244353; int n,a[MAXN],b[MAXN]; int f[MAXN][MAXN]; int sma,smb; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } int fac[MAXN],inv[MAXN]; int main(){ fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha; inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha; scanf("%d",&n); FOR(i,1,n) scanf("%d%d",a+i,b+i); FOR(i,1,n) sma += a[i],smb += b[i]-1; f[0][0] = -1; FOR(i,1,n){ ROF(j,sma,a[i]){ ROF(k,smb,0){ ROF(x,std::min(k,b[i]-1),0){ add(f[j][k],(ha-1ll*f[j-a[i]][k-x]*inv[x]%ha*qpow(a[i],x)%ha)%ha); } } } } int ans = 0; FOR(j,0,sma) FOR(k,0,smb){ int gx = f[j][k]; gx = 1ll*gx*fac[k]%ha*sma%ha; gx = 1ll*gx*qpow(qpow(j,k+1))%ha; add(ans,gx); } printf("%d\n",ans); return 0; }F题意给定两个长度为 $n$ 的排列 $P,Q$，要求你构造两个长度为 $n$ 的排列 $A,B$，满足：$A_i$ 取值 $\{i,P_i\}$$B_i$ 取值 $\{i,Q_i\}$要求 $A,B$ 不同的位置尽量多，求出这个最多的位置个数。题解将 $P,Q$ 分成若干个环，同一个环要么都取 $i$ 要么都取 $P_i/Q_i$。讨论一下 $P_i,Q_i$ 之间的关系，可以得到以下情况：$P_i=Q_i=i$：无论如何都相等。$P_i,Q_i \neq i,P_i \neq Q_i$：同时不转相等。$P_i=i,Q_i \neq i$：$B_i$ 不转相等。$P_i \neq i,Q_i = i$：$A_i$ 不转相等。$P_i=Q_i,P_i,Q_i \neq i$：同时转相等。网络流。把 $B$ 倒过来就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; struct Edge{ int to,w,nxt; }e[MAXN<<4]; int head[MAXN],cnt=1,cur[MAXN],dep[MAXN]; inline void add(int u,int v,int w){ e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt; e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt; } int S,T,N; inline bool bfs(){ FOR(i,0,N) cur[i] = head[i],dep[i] = 0; std::queue<int> q;q.push(S);dep[S] = 1; while(!q.empty()){ int v = q.front();q.pop(); for(int i = head[v];i;i = e[i].nxt){ if(e[i].w > 0 && !dep[e[i].to]){ dep[e[i].to] = dep[v]+1; q.push(e[i].to); } } } return dep[T]; } inline int dfs(int v,int lim=1e9){ if(v == T) return lim; if(!lim) return 0; int ans = 0; for(int &i = cur[v];i;i = e[i].nxt){ if(e[i].w > 0 && dep[e[i].to] == dep[v]+1){ int t = dfs(e[i].to,std::min(lim,e[i].w)); if(t > 0){ ans += t; e[i].w -= t; e[i^1].w += t; lim -= t; if(!lim) break; } } } return ans; } inline int Dinic(){ int ans = 0,flow; while(bfs()) while((flow=dfs(S))) ans += flow; return ans; } int n,p[MAXN],q[MAXN]; bool vis[MAXN]; int belp[MAXN],belq[MAXN]; inline void dfs(int v,int now,int p[],int bel[]){ vis[v] = 1;bel[v] = now; if(vis[p[v]]) return; dfs(p[v],now,p,bel); } int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",p+i),++p[i]; FOR(i,1,n) scanf("%d",q+i),++q[i]; FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,p,belp); FOR(i,1,n) vis[i] = 0; FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,q,belq); S = N+1;T = N+2;N = T; int ans = n; FOR(i,1,n){ if(p[i] == q[i]){ if(p[i] == i){ ans--;continue; } else{ add(belp[i],belq[i],1); add(belq[i],belp[i],1); } } else{ if(p[i] == i && q[i] != i){ add(belq[i],T,1); } else if(p[i] != i && q[i] == i){ add(S,belp[i],1); } else{ add(belq[i],belp[i],1); } } } printf("%d\n",ans-Dinic()); return 0; } /* p: 割左边=不转 右边=转 q反过来 何时答案会-1: p[i]=q[i]=i 无论如何都会-1 p[i],q[i] != i 同时不转 p[i]=i,q[i]!=i 2不转 p[i]!=i,q[i]=i 1不转 p[i]=q[i],p[i],q[i]!=i 同时转 */
B 被降智了，所以掉分了。A考虑将这个串拆成三部分考虑：114，5，14。设 $f_{i,j}$ 表示 114 的 $4$ 的位置是 $i$，1 代表 $j$ 的方案数，$g_{i,j}$ 表示 14 中 1 的位置是 $i$，4 代表 $j$ 的方案数，另外记录一个 $s_{i,j}$ 表示前 $i$ 个字符中 $j$ 的数量，字符串是 $a$，那么答案是：$$ \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times (j-i-1-(s_{j-1,a_i}-s_{i,a_i})-(s_{j-1,a_j}-s_{i,a_j})) $$我们考虑将这个式子拆成可以分开维护的形式：$$ \begin{aligned} \sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(j-1-s_{j-1,a_i}-s_{j-1,a_j})\\ +\sum_{i < j} f_{i,a_j}\times g_{j,a_i} \times(-i+s_{i,a_i}+s_{i,a_j})\\ \end{aligned} $$我们枚举 $i$ 和 $a_j$，维护对应的 $\sum g_{j,a_i}\times (j-1-s_{j-1,a_i}-s_{j-1,a_j})$ 和 $\sum g_{j,a_i}$ 即可。可以用一些滚动数组技巧做到空间 $O((\Sigma) ^2)$。放个卡完空间的代码：#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; const int ha = 114514; char str[MAXN]; int n; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int sm1[26][26],sm2[26][26]; int smf[26],smg[26]; int main(){ scanf("%s",str+1);n = strlen(str+1); auto f = [&](int i,int j){ return str[i]-'a' == j ? 0 : (1ll*smf[j]*(smf[j]-1)/2)%ha; }; auto g = [&](int i,int j){ return str[i]-'a' == j ? 0 : smg[j]; }; int ans = 0; FOR(i,1,n-1) add(smf[str[i]-'a'],1); ROF(i,n,1){ FOR(j,0,25){ if(str[i]-'a' == j) continue; add(ans,1ll*f(i,j)*sm2[j][str[i]-'a']%ha); int coe = (smf[j]+smf[str[i]-'a']+1-i+ha)%ha; coe = 1ll*coe*f(i,j)%ha; add(ans,1ll*coe*sm1[j][str[i]-'a']%ha); } FOR(j,0,25){ add(sm1[str[i]-'a'][j],g(i,j)); int coe = (i-1-smf[j]-smf[str[i]-'a']+ha+ha)%ha; add(sm2[str[i]-'a'][j],1ll*g(i,j)*coe%ha); } if(i-1) add(smf[str[i-1]-'a'],ha-1); add(smg[str[i]-'a'],1); } printf("%d\n",ans); return 0; }B这个题没有括号！！表达式求值没有括号要考虑按照某个运算分成若干块处理。我们按照或运算将表达式分成很多段，每一段都是一堆与运算拼起来的，对于每一段，这一段是 $1$ 的条件形如某些数必须是 $1$，某些数必须是 $0$，某些数无限制，所以可以用三进制来存储。然后或的意思就是把这些东西并起来。然后具体将这些限制对应的每个方案上的时候，用个高维前缀和就好了。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e6 + 5; const int MAXM = 15 + 3; int n,m; char F[MAXN]; char str[MAXN]; int a[MAXN]; // and = 16 or = 17 // const 0 = 18 const 1 = 19 int pw[MAXM]; bool f[43046721+233]; int cnt[MAXM]; int trans[(1<<MAXM)+3]; int main(){ pw[0] = 1;FOR(i,1,MAXM-1) pw[i] = pw[i-1]*3; scanf("%d",&m);scanf("%s",F); trans[0] = 0;FOR(i,1,(1<<m)-1) trans[i] = trans[i>>1]*3+(i&1); int now = 0; while(true){ scanf("%s",str+1); if(str[1] == 'E') break; if(str[1] == 'N'){now ^= 1;continue;} if(str[1] == 'A' || str[1] == 'O') a[++n] = 16+(str[1]=='O'); if(str[1] == 'a'){ int len = strlen(str+1),id = 0; FOR(i,2,len) id = id*10+str[i]-'0'; id = m-id+1; a[++n] = (now?-1:1)*id; now = 0; } if(str[1] == '0' || str[1] == '1'){ a[++n] = 18+((str[1]=='1')^now); now = 0; } } int lst = 1; std::vector S; FOR(i,2,n){ if(a[i] == 17){ S.pb(MP(lst,i-1)); lst = i+1; } } S.pb(MP(lst,n)); // 0=0 // 1=1 // 2=no limit for(auto x:S){ CLR(cnt,-1); bool flag = 1; FOR(i,x.fi,x.se){ if(a[i] == 16) continue; if(a[i] == 18 || a[i] == 19){flag &= (a[i]==19);continue;} int t = std::abs(a[i]),sgn = a[i]>0; if(cnt[t] == -1) cnt[t] = sgn; else flag &= (!(cnt[t]^sgn)); } if(!flag) continue; int zt = 0; FOR(i,1,m){ if(cnt[i] == -1) cnt[i] = 2; zt += cnt[i]*pw[i-1]; } f[zt] = 1; } FOR(i,0,m-1){ FOR(S,0,pw[m]){ f[S] |= f[S-((S/pw[i])%3)*pw[i]+2*pw[i]]; } } bool flag = 1; FOR(S,0,(1<<m)-1) flag &= (f[trans[S]]==F[S]-'0'); puts(flag?"YES":"NO"); return 0; }C代价等价于路径最小值乘路径长度。边分治，预处理出每个点到根的最小值 $mn_i$ 和距离 $d_i$，考虑两个点 $i,j$，如果 $mn_i \leq mn_j$ 贡献就是 $(d_i+d_j)mn_i$，这个相当于是求 $d_j$ 的后缀最大值；如果 $mn_i > mn_j$ 就是 $(d_i+d_j)mn_j$，相当于是个二次函数求最值，搞个凸包就行了。注意两点：凸包排序的时候第二维要按照 $y$ 坐标对应排序，不然会锅边分治的时候不能同时维护点的信息，三度化之后路径上的点信息都被破坏了，我们要把点的信息转到边上，对应到这题就是每个边的边权是相邻两个点的较小值，然后实边距离为 $1$，虚边距离为 $0$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,a[MAXN]; struct Edge{ int to,w1,w2,nxt; }e[MAXN<<1]; int head[MAXN],cnt = 1; inline void add(int u,int v,int w1,int w2){ e[++cnt] = (Edge){v,w1,w2,head[u]};head[u] = cnt; e[++cnt] = (Edge){u,w1,w2,head[v]};head[v] = cnt; } std::vector<int> G[MAXN]; int _n; inline void dfs(int v,int fa=0){ int las = v; for(auto x:G[v]){ if(x == fa) continue; add(las,x,std::min(a[v],a[x]),1);++n;add(las,n,1e9,0);las = n; } for(auto x:G[v]){ if(x == fa) continue; dfs(x,v); } } int rt,mx[MAXN]; int sz[MAXN]; bool vis[MAXN]; inline void getroot(int v,int fa=0){ sz[v] = 1; for(int i = head[v];i;i = e[i].nxt){ if(e[i].to == fa || vis[i>>1]) continue; getroot(e[i].to,v);sz[v] += sz[e[i].to]; mx[i>>1] = std::max(sz[e[i].to],mx[0]-sz[e[i].to]); rt = mx[rt] < mx[i>>1] ? rt : i>>1; } } struct Node{ LL x,y; Node(LL x=0,LL y=0) : x(x),y(y) {} inline Node operator - (const Node &t) const {return Node(x-t.x,y-t.y);} inline LL operator * (const Node &t) const {return x*t.y-y*t.x;} }; LL ans[MAXN]; struct node{ int dis,mn,id; node(int dis=0,int mn=0,int id=0) : dis(dis),mn(mn),id(id) {} inline bool operator < (const node &t) const {// 保证凸包正确性 return mn < t.mn || mn == t.mn && dis > t.dis; } }; std::vector<node> ls,rs; inline void dfs2(int o,int v,int dep=1,int val=1e9,int fa=0){ if(v <= _n) (o?rs:ls).pb(node(dep,std::min(val,a[v]),v)); for(int i = head[v];i;i = e[i].nxt){ if(e[i].to == fa || vis[i>>1]) continue; dfs2(o,e[i].to,dep+e[i].w2,std::min(val,e[i].w1),v); } } int suf[MAXN]; std::vector<Node> cov; inline LL get(const Node &v,int x){ return -v.x*x+v.y; } bool flag = 0; inline LL query(int x){ if(cov.empty()) return 0; if(cov.size() == 1) return get(cov[0],x); int l = 0,r = (int)cov.size()-2;LL ans = get(cov.back(),x); while(l <= r){ int mid = (l + r) >> 1; LL ls = get(cov[mid],x),rs = get(cov[mid+1],x); if(ls <= rs) ans = std::max(ans,rs),l = mid+1; else ans = std::max(ans,ls),r = mid-1; } return ans; } inline void solve(std::vector<node> &L,std::vector<node> &R){// L <- R if(L.empty() || R.empty()) return; suf[R.size()] = 0; ROF(i,(int)R.size()-1,0) suf[i] = std::max(suf[i+1],R[i].dis); int ps = 0; for(auto x:L){ while(ps < R.size() && R[ps].mn < x.mn) ++ps; ans[x.id] = std::max(ans[x.id],1ll*(suf[ps]+x.dis)*x.mn); } ps = 0;cov.clear(); for(auto x:L){ while(ps < R.size() && R[ps].mn < x.mn){ Node p = Node(-R[ps].mn,1ll*R[ps].mn*R[ps].dis); while(cov.size() >= 2 && (cov.back()-cov[(int)cov.size()-2])*(p-cov.back()) <= 0) cov.pop_back(); cov.pb(p); ++ps; } ans[x.id] = std::max(ans[x.id],query(x.dis)); } cov.clear(); } inline void work(int edge){ if(!edge) return; int u = e[edge<<1].to,v = e[edge<<1|1].to; vis[edge] = 1;dfs2(0,u,1,e[edge<<1].w1);dfs2(1,v,e[edge<<1].w2,e[edge<<1].w1); std::sort(all(ls));std::sort(all(rs)); solve(ls,rs);solve(rs,ls); ls.clear();rs.clear(); mx[rt = 0] = sz[u];getroot(u);work(rt); mx[rt = 0] = sz[v];getroot(v);work(rt); } int main(){ scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),ans[i] = a[i];_n = n; FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } dfs(1); mx[rt = 0] = n;getroot(1); work(rt); FOR(i,1,_n) printf("%lld%c",ans[i]," \n"[i==_n]); return 0; }
A打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl int main(){ int n,k;scanf("%d%d",&n,&k); puts(k==1&&(!(n&1)) ? "yrrebxaw":"qjd"); return 0; }B求出每个边的存活时间，线段树分治即可，写个支持撤销的并查集。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; const int ha = 1e9 + 7; int f[MAXN],sz[MAXN],inv[MAXN],now = 1; inline int find(int x){ return x == f[x] ? x : find(f[x]); } struct Node{ int x,y,z; Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {} }; std::vector<Node> opt; inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; if(sz[x] > sz[y]) std::swap(x,y); now = 1ll*now*inv[sz[x]]%ha; now = 1ll*now*inv[sz[y]]%ha; opt.pb(Node(x,y,sz[x])); sz[y] += sz[x];f[x] = y; now = 1ll*now*sz[y]%ha; } inline void undo(){ Node v = opt.back();opt.pop_back(); now = 1ll*now*inv[sz[v.y]]%ha; f[v.x] = v.x;sz[v.x] = v.z;sz[v.y] -= v.z; now = 1ll*now*sz[v.x]%ha; now = 1ll*now*sz[v.y]%ha; } std::vector G[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void modify(int x,int l,int r,int L,int R,P d){ if(l == L && r == R){ G[x].pb(d); return; } int mid = (l + r) >> 1; if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); } int ans[MAXN]; inline void dfs(int x,int l,int r){ int t = opt.size(); for(auto v:G[x]) merge(v.fi,v.se); if(l == r){ ans[l] = now; while(t != opt.size()) undo(); return; } int mid = (l + r) >> 1; dfs(lc,l,mid);dfs(rc,mid+1,r); while(t != opt.size()) undo(); } int n,m; int s[MAXN],e[MAXN]; int main(){ // freopen("B.in","r",stdin); //freopen("B.out","w",stdout); inv[1] = 1; FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha; scanf("%d%d",&n,&m); FOR(i,1,n) f[i] = i,sz[i] = 1; std::map<P,int> S; FOR(i,1,m){ int o,u,v;scanf("%d%d%d",&o,&u,&v); if(u > v) std::swap(u,v); if(o == 1){ S[MP(u,v)] = i; } else{ modify(1,1,m,S[MP(u,v)],i-1,MP(u,v)); S.erase(MP(u,v)); } } for(auto x:S) modify(1,1,m,x.se,m,x.fi); dfs(1,1,m); FOR(i,1,m) printf("%d\n",ans[i]); return 0; }C主要是普及一下排列如何 $O(n \log n)$ 求三维偏序：给定三个排列 $a_i,b_i,c_i$，我们要求$$ \sum_{i,j} [a_i < a_j][b_i < b_j][c_i < c_j] $$由于是排列，不难发现有$$ \sum_{i,j} [a_i < a_j][b_i < b_j][c_i < c_j] = \sum_{i,j}[a_i > a_j][b_i > b_j][c_i > c_j] $$并且排列中不会有相等关系，所以 $[a \leq b] = [a < b],[a \geq b] = [a > b]$，考虑将上述求的东西容斥，需要算的就只有若干个二维偏序和一维偏序问题了。对于这个题我们考虑硬算期望：首先对于两个都不是 $-1$ 的位置，就是一个三维偏序。然后对于两个都是 $-1$ 的位置，如果满足 $i<j,p_i < p_j$，就有 $\frac{1}{2}$ 的概率是 $q_i<q_j$，所以这个就是个二维数点，答案乘上 $\frac{1}{2}$。对于一个是 $-1$ 一个不是的位置，可以预处理没有用过的数中有多少个比某个数 $x$ 大/小的，然后写下式子也是二维数点问题。题解的做法是直接对上述容斥式子套期望线性性，就比较简单。。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(register int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } int n,p[MAXN],q[MAXN]; const int ha = 998244353; int inv[MAXN]; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } struct BIT{ #define lowbit(x) ((x)&(-(x))) int tree[MAXN],ts[MAXN],now; inline void reset(){++now;} inline void add(int pos,int x){ while(pos < MAXN){ if(ts[pos] != now) ts[pos] = now,tree[pos] = 0; ::add(tree[pos],x); pos += lowbit(pos); } } inline int query(int pos){ int res = 0; while(pos){ if(ts[pos] != now) ts[pos] = now,tree[pos] = 0; ::add(res,tree[pos]); pos -= lowbit(pos); } return res; } }bit; int ans = 0; struct Node{ int x,y,z; Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {} inline bool operator < (const Node &t) const { return x < t.x; } }a[MAXN]; inline int work2(int n){ bit.reset(); // std::sort(a+1,a+n+1); int res = 0; FOR(i,1,n){ add(res,bit.query(a[i].y)); bit.add(a[i].y,1); } return res; } inline void work(int n){// 单 log 三维偏序 ans = 1ll*n*(n-1)%ha; add(ans,ha-3ll*n%ha*(n-1)%ha*inv[2]%ha); std::sort(a+1,a+n+1); add(ans,work2(n));// (x,y,z) FOR(i,1,n) std::swap(a[i].x,a[i].z); std::sort(a+1,a+n+1); add(ans,work2(n));// (z,y,x) FOR(i,1,n) std::swap(a[i].y,a[i].z); add(ans,work2(n));// (z,x,y) ans = 1ll*ans*inv[2]%ha; // int t = 0; // FOR(i,1,n) FOR(j,1,n) if(i != j && a[i].x < a[j].x && a[i].y < a[j].y && a[i].z < a[j].z) ++t; // DEBUG(t); } int nxt[MAXN],pre[MAXN]; int main(){ // freopen("C.in","r",stdin); // freopen("C.out","w",stdout); read(n);FOR(i,1,n) read(p[i]);FOR(i,1,n) read(q[i]); inv[1] = 1;FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha; int m = 0; // part 1 FOR(i,1,n) if(q[i] != -1) a[++m] = Node(i,p[i],q[i]); work(m); // part 2 m = n-m; bit.reset(); FOR(i,1,n){ if(q[i] != -1) continue; add(ans,1ll*bit.query(p[i])*inv[2]%ha); bit.add(p[i],1); } // part 3 FOR(i,1,n) if(q[i] != -1) nxt[q[i]] = 1; FOR(i,1,n) nxt[i] ^= 1,pre[i] = nxt[i]; ROF(i,n,1) nxt[i] += nxt[i+1]; FOR(i,1,n) pre[i] += pre[i-1]; bit.reset(); FOR(i,1,n){ if(q[i] == -1){ add(ans,bit.query(p[i])); } else{ bit.add(p[i],1ll*nxt[q[i]]*inv[m]%ha); } } bit.reset(); FOR(i,1,n){ if(q[i] == -1){ bit.add(p[i],1); } else{ add(ans,1ll*bit.query(p[i])*pre[q[i]]%ha*inv[m]%ha); } } printf("%d\n",ans); return 0; }D先考虑策略是什么，考试的时候我没有注意到这个事实：后手可以等先手钻进某个角落自闭的时候慢慢把所有道路清掉，就以为策略之间很麻烦。。那么我们考虑以 $t$ 为根，那么这个策略大概是先手往上爬，爬到某个位置后钻进子树内，然后就自闭了，这时后手把路上的边都删掉，然后让先手精确地到达 $t$。我们设 $f_v$ 表示从 $v$ 点钻进去的代价，那么如果先手考虑从 $v$ 点钻进去，后手肯定会先 ban 掉最大的 $f_x$，其中 $x \in son_v$。我们考虑二分答案，每次暴力从 $s$ 到 $t$ 往上条，到每个点判断一下是否从某个儿子钻进去之后代价会 $>mid$，如果会的话就一定要删掉，这里代价计算的时候有点细节。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; std::vector<int> G[MAXN]; int n,s,t; int f[MAXN],fa[MAXN],sm[MAXN]; inline void dfs(int v,int fa=0){ int mx = 0,cmx = 0,deg = (int)G[v].size()-(fa!=0);::fa[v] = fa; for(auto x:G[v]){ if(x == fa) continue; sm[x] = sm[v]+(v==t?0:deg-1); dfs(x,v); if(f[x] > mx){ cmx = mx;mx = f[x]; } else if(f[x] > cmx){ cmx = f[x]; } } if(!deg) f[v] = 0; else if(deg == 1) f[v] = 1; else f[v] = cmx+deg; } inline bool chk(int lim){// 花费不超过 lim 到根 int v = s,las = -1,now = 0,r = 1; while(v != t){ // 枚举在哪个点钻进去 int cnt = 0; for(auto x:G[v]){ if(x == fa[v] || x == las) continue; cnt += (now+f[x]+1+sm[x]-(v!=s) > lim); } now += cnt; if(now > r || now > lim) return 0; v = fa[las=v];++r; } return 1; } int main(){ scanf("%d%d%d",&n,&t,&s); if(s == t) return puts("0"),0; FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } dfs(t); int l = 0,r = 2*n,ans = -1; while(l <= r){ int mid = (l + r) >> 1; if(chk(mid)) ans = mid,r = mid-1; else l = mid+1; } printf("%d\n",ans); return 0; }
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXM = 60; LL f[MAXM+1],pw[MAXM+1]; int main(){ pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1; LL n;scanf("%lld",&n); FOR(i,1,MAXM){ FOR(j,0,i){// 结尾有多少个 1 f[i] += 1ll*(j+1)*pw[std::max(0,i-j-1)]; } } LL ans = 0; ROF(i,MAXM,0){ if(!((n>>i)&1)) continue; ans += f[i]; } if(n&1) ans++; printf("%lld\n",ans); return 0; } // [0,n-1] 偶数贡献 1 奇数贡献末尾连续 1 数量+1B.先考虑 $n=2$ 怎么做：我们设 $f_{a,b}$ 表示剩 $a$ 个颜色 $1$，$b$ 个颜色 $2$ 的答案是什么。我们设放在颜色 $1$ 上的钱为 $x$，颜色 $2$ 上的必然为 $1-x$，所以能得到的钱是 $\min(2xf_{a-1,b},2(1-x)f_{a,b-1})$。能解出来 $x=\frac{f_{a,b-1}}{f_{a-1,b}+f_{a,b-1}}$，也就是有方程 $f_{a,b} = \frac{2f_{a-1,b}f_{a,b-1}}{f_{a-1,b}+f_{a,b-1}}$。那么我们设 $g_{a,b} = f_{a,b}2^{a+b}$，有转移方程 $g_{a,b} = \frac{g_{a-1,b}g_{a,b-1}}{g_{a-1,b}+g_{a,b-1}}$，考虑两边取倒数，也就是$$ \frac{1}{g_{a,b}} = \frac{g_{a-1,b}+g_{a,b-1}}{g_{a-1,b}g_{a,b-1}} = \frac{1}{g_{a-1,b}}+\frac{1}{g_{a,b-1}} $$我们发现 $\frac{1}{g_{a,b}}$ 实际上是从 $(0,0)$ 走到 $(a,b)$ 的方案数，也就是 $\binom {a+b}{a}$。这样就能通过 $n=2$ 的部分。$n>2$ 的部分：我们考虑写出类似的状态：也就是有 $n$ 维。这个倒数也等价于从 $(0,0,\ldots,0)$ 走到 $(a_1,a_2,\ldots,a_n)$ 的方案数，也就是 $\binom{\sum_i a_i}{a_1,a_2,\ldots,a_n}$，所以答案就是 $\frac{n^{\sum_i a_i}}{\binom{\sum_i a_i}{a_1,a_2,\ldots,a_n}}$。比赛的时候解出了不等式就是按照比值取，相当于先手策略确定了，所以直接按照后手整个小根堆贪心。。然而式子是一样的。。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; const int ha = 998244353; int n,a[MAXN]; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } /* //int f[1005][1005]; double f[1005][1005],g[1005][1005]; int mx = 0; namespace BF{ inline void Solve(){ f[0][0] = 1; FOR(i,1,10) f[i][0] = f[0][i] = 2*f[i-1][0]; FOR(i,1,10){ FOR(j,1,10){ f[i][j] = 2.0*f[i][j-1]*f[i-1][j]/(f[i-1][j]+f[i][j-1]); g[i][j] = 1.0*f[i][j-1]/(f[i-1][j]+f[i][j-1]); // f[i][j] = 2ll*f[i][j-1]%ha*f[i-1][j]%ha*qpow((f[i-1][j]+f[i][j-1])%ha)%ha; } } FOR(i,1,10){ FOR(j,1,10){ printf("%.5f=%.5f%c",f[i][j],1.0*i/(i+j)," \n"[j==10]); } } } } */ int main(){ std::priority_queue<int,std::vector<int>,std::greater<int> > q; int sm = 0; scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),q.push(a[i]),sm += a[i]; int ans = 1; while(!q.empty()){ int v = q.top();q.pop(); ans = 1ll*ans*n%ha*qpow(sm)%ha*v%ha; --v;if(v) q.push(v);--sm; } printf("%d\n",ans); return 0; } // 策略: 按照比例分配C套路题。我们有：$$ x^{k} = \sum_{i = 0}^k \left[^k_i\right] x^{\underline i} $$相当于对于每个 $i$，计算每一条路径的贡献的和，一条长度为 $len$ 的路径的贡献是 $\binom{len} i i!$，也就是有序选出 $i$ 个不同的边。于是可以搞个 dp 了：设 $f_{v,i}$ 表示 $v$ 点，端点一个点是 $v$ ，另一个点在子树内的所有的长度为 $i$ 的链的选取方案，转移直接从儿子合并上来就行。我们在转移的过程中会得到 $g_{x,i}$ 表示加了到父亲 $v$ 的边后的选取方案，那么所以 $lca = v$ 的链是至多用两个儿子的 $g$ 拼起来的，写个树形背包就行了。根据树形背包的复杂度来说，复杂度是 $O(nk)$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; const int MAXM = 100 + 5; const int ha = 998244353; inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int S2[MAXM][MAXM],C[MAXM][MAXM]; inline void prework(){ S2[0][0] = 1;C[0][0] = 1; FOR(i,1,MAXM-1){ C[i][0] = 1; FOR(j,1,i){ S2[i][j] = (S2[i-1][j-1]+1ll*S2[i-1][j]*j%ha)%ha; C[i][j] = (C[i-1][j]+C[i-1][j-1])%ha; } } } int n,k; std::vector<int> G[MAXN]; int f[MAXN][MAXM],tmp[MAXM]; int h[MAXM]; int sz[MAXN]; inline void dfs(int v,int fa=0){ f[v][0] = 1;sz[v] = 1; for(auto x:G[v]){ if(x == fa) continue; dfs(x,v); } for(auto x:G[v]){ if(x == fa) continue; FOR(i,0,k){ tmp[i] = f[x][i]; if(i) add(tmp[i],1ll*f[x][i-1]*i%ha); } // 任选两个合并 FOR(a,0,std::min(k,sz[v])){ FOR(b,0,std::min(k,sz[x])){ if(a+b > k) break; add(h[a+b],1ll*f[v][a]*tmp[b]%ha*C[a+b][b]%ha); } } FOR(i,0,k) add(f[v][i],tmp[i]); sz[v] += sz[x]; } } int main(){ // freopen("C.in","r",stdin); prework(); read(n);read(k); FOR(i,2,n){ int u,v;read(u);read(v); G[u].pb(v);G[v].pb(u); } dfs(1); int ans = 0; FOR(i,0,k){ int gx = 1ll*h[i]*S2[k][i]%ha; add(ans,gx); } printf("%d\n",ans); return 0; }D注意：本题空间限制 256 M。这个树上的问题肯定是强于链上的问题的，所以我们要考虑根号分治。对于 $x \leq \sqrt n$ 的部分：我们可以枚举每一个 $x$ ，分别计算操作对所有询问的贡献，如果确定了 $u$ 是 $v$ 的祖先，并且有操作 $(u,x,y,z)$，那么这个操作对询问 $v$ 有影响当且仅当 $dep_v \equiv dep_u+y \pmod x$，所以我们再按照 $\bmod x$ 的值分组，每组内相当于就只有子树限制了。需要支持区间加和单点查询，如果直接做复杂度会变成 $O(n\sqrt n \log n)$，但是我们发现我们的修改有 $O(q)$ 次，询问有 $O(q \sqrt n)$ 次（对于每个 $x$ 都要把所有询问放进去），所以可以用一个 $O(\sqrt n)$ 修改，$O(1)$ 查询的东西将复杂度平衡到 $O(q\sqrt n)$。对于 $x > \sqrt n$ 的部分：相当于我们可以暴力将每个操作 apply 到所有可能的深度上，并且将询问挂在对应的深度上，对于每个深度，我们现在只有了子树限制，相当于要支持区间加，单点查。我们发现修改的次数有 $O(q\sqrt n)$ 次（每个操作会贡献到 $O(\sqrt n)$ 个深度上），查询的次数只有 $O(q)$ 次，所以我们将询问差分一下，变成了 $O(q\sqrt n)$ 次单点修改，$O(q)$ 次前缀查询，也可以用分块根号平衡到 $O(q \sqrt n)$。但是我们发现我们如果对于每个深度都存下来有关于它的所有修改操作显然就爆炸了。。空间复杂度是 $O(q \sqrt n)$ 的，但是我们注意到每个操作贡献到的两个深度的差至少是 $\sqrt n$ ，所以我们可以每 $\sqrt n$ 个深度一起处理，每次只存这些深度的询问和修改，这样总复杂度还是 $O(q\sqrt n)$ 的，并且空间复杂度降到了 $O(q+n)$。注意有个细节：如果你的根号数据结构实现的 reset （清空）是存下所有操作并反向做的话，并且是在 modify 开头将操作加入 vector 的话，用 vector 记录的时候不要把删除操作加入 vector！！这样导致在遍历一个 vector 的时候加入新元素，会 UB。。。调了一下午。。主要是 Mac 测不出来这个错误，并且 OJ 上还能过大部分点。。还要注意：vector 的 clear 不会释放空间，要用 std::vector<element>().swap。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 4e5 + 5; inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } struct DS1{// 区间加O(sqrt) 单点查O(1) int B,N; int tag[MAXN],bel[MAXN],a[MAXN]; std::vector<std::pair<P,int> > S; inline void init(int size){ N = size;B = std::sqrt(1.0*N);S.clear(); FOR(i,1,N) bel[i] = (i-1)/B+1,a[i] = 0; FOR(i,1,bel[N]) tag[i] = 0; } inline void modify(int l,int r,int d,bool tg=1){ if(tg) S.pb(MP(MP(l,r),d)); if(bel[l] == bel[r]){ FOR(i,l,r) a[i] += d; return; } FOR(i,l,bel[l]*B) a[i] += d; FOR(i,bel[l]+1,bel[r]-1) tag[i] += d; FOR(i,(bel[r]-1)*B+1,r) a[i] += d; } inline int query(int x){ return tag[bel[x]]+a[x]; } inline void reset(){ for(auto x:S) modify(x.fi.fi,x.fi.se,-x.se,0); //std::vector<std::pair<P,int> >().swap(S); S.clear(); } }ds1; struct DS2{ int B,N; int a[MAXN],sm[MAXN],bel[MAXN]; std::vector<std::pair<P,int> > S; inline void init(int size){ N = size;B = std::sqrt(1.0*N);S.clear(); FOR(i,1,N) bel[i] = (i-1)/B+1,a[i] = 0; FOR(i,1,bel[N]) sm[i] = 0; } inline void modify(int l,int r,int d,int tg=1){ if(tg) S.pb(MP(MP(l,r),d)); a[l] += d;sm[bel[l]] += d;++r; if(r <= N) a[r] -= d,sm[bel[r]] -= d; } inline int query(int x){ int res = 0; FOR(i,1,bel[x]-1) res += sm[i]; FOR(i,(bel[x]-1)*B+1,x) res += a[i]; return res; } inline void reset(){ for(auto x:S) modify(x.fi.fi,x.fi.se,-x.se,0); //std::vector<std::pair<P,int> >().swap(S); S.clear(); } }ds2; int n,m; std::vector<int> G[MAXN]; int dep[MAXN],dfn[MAXN],sz[MAXN]; inline void dfs(int v,int fa=0){ static int ts = 0; dfn[v] = ++ts;dep[v] = dep[fa]+1;sz[v] = 1; for(auto x:G[v]){ if(x == fa) continue; dfs(x,v);sz[v] += sz[x]; } } struct Node{ int opt,v,x,y,z,id; Node(int opt=0,int v=0,int x=0,int y=0,int z=0,int id=0) : opt(opt),v(v),x(x),y(y),z(z),id(id) {} }q[MAXN]; int tot; std::vector<Node> qq[MAXN]; int ans[MAXN]; int main(){ // freopen("D.in","r",stdin); // freopen("D.out","w",stdout); read(n);read(m); FOR(i,2,n){ int u,v;read(u);read(v); G[u].pb(v);G[v].pb(u); } dfs(1); FOR(i,1,m){ read(q[i].opt);read(q[i].v); if(q[i].opt == 1) read(q[i].x),read(q[i].y),read(q[i].z); q[i].id = i; } int B = std::sqrt(1.0*n); ds1.init(n);ds2.init(n); FOR(x,1,B){ tot = 0; FOR(i,1,m){ if(q[i].opt == 1){ if(q[i].x == x) qq[(q[i].y+dep[q[i].v])%x].pb(q[i]); } else{ qq[dep[q[i].v]%x].pb(q[i]); } } FOR(y,0,x-1){ ds1.reset(); for(auto v:qq[y]){ if(v.opt == 1) ds1.modify(dfn[v.v],dfn[v.v]+sz[v.v]-1,v.z); else ans[v.id] += ds1.query(dfn[v.v]); } } FOR(i,0,x-1) qq[i].clear(); // FOR(i,0,x-1) std::vector<Node>().swap(qq[i]);//qq[i].clear(); } // FOR(i,0,B) std::vector<Node>().swap(qq[i]); // 卡空间 考虑每次只处理[l,l+B]深度的询问 这样每个操作最多进来一次 // 毒瘤出题人！！！ for(int l = 1,r;l <= n;l = r+1){ r = std::min(n,l+B); FOR(i,1,m){ if(q[i].opt == 1){ if(q[i].x > B && r >= dep[q[i].v]+q[i].y){ int k = (r-q[i].y-dep[q[i].v])/q[i].x; int d = k*q[i].x+q[i].y+dep[q[i].v]; while(l <= d) qq[d].pb(q[i]),d -= q[i].x; } } else if(dep[q[i].v] >= l && dep[q[i].v] <= r) qq[dep[q[i].v]].pb(q[i]); } FOR(i,l,r){ ds2.reset(); for(auto x:qq[i]){ if(x.opt == 1) ds2.modify(dfn[x.v],dfn[x.v]+sz[x.v]-1,x.z); else ans[x.id] += ds2.query(dfn[x.v]); } } FOR(i,l,r) std::vector<Node>().swap(qq[i]);//qq[i].clear(); // 注意:vector clear 不会释放空间 } FOR(i,1,m) if(q[i].opt == 2) printf("%d\n",ans[i]); return 0; }
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的往右走，那么之后一定有一次往左走，并且跨越起点的，我们可以一开始就走到这个点，答案不会变劣。所以我们的路径只有可能是先往右最多走一次，再往左走。我们观察一下一个点 $v$ 到达左边的点 $x$ 的最短距离的分布是怎么样的：如果 $dis(v,x)=1$，那么有 $l_v \leq x$。如果 $dis(v,x) \leq 2$，那么我们就会先走一步，用这个点中转，也就是问在区间 $[l_v,n]$ 内是否存在点 $y$，使得 $dis(x,y) \leq 1$。注意这里这个区间包含了一些根本不跨过 $v$ 的点，但这是显然不影响答案的。归纳可以得到：如果 $dis(v,x) \leq k$，当且仅当存在一个点 $y \in [l_v,n]$，满足 $dis(x,y) \leq k-1$。所以一个暴力的想法是每次先特判了距离为 $1$ 的点，然后每次求出最往左的距离为 $2$ 的点跳过去，以此类推。。对于跳这种东西，我们肯定想到要用倍增优化。我们想找到 $\leq k$ 的最往左的点，就要找到 $dis(x,y) \leq k-1$ 的最往左的点。。。所以我们定义在找 $dis(v,x) \leq k$ 的一次跳跃是从 $x$ 点找到最小的一个点 $z$，满足 $\exists y \in [l_v,n],dis(z,y) \leq k-1$，所以设 $f_{i,j}$ 表示从 $i$ 号点，跳了 $2^j$ 次（也就是处理了距离为 $[1,2^j+1]$ 的点），为了统计答案，设 $g_{i,j}$ 表示从 $i$ 号点跳了 $2^j$ 的所有答案，初始化 $f_{i,0} = \min_{j \geq i}\{l_j\}$，$f_{1,0} = 0,g_{i,0} = i-f_{i,0}$。转移大概写一下 ：$$ \begin{aligned} f_{i,j} &= f_{f_{i,j-1},j-1}\\ g_{i,j} &= g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j}) \end{aligned} $$查询的时候跳一下，记一下已经跳了多少长度即可。最后有一些零散的边界要判掉。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int MAXM = 18; int n,l[MAXN]; // 处理[i,n]跳2^j步的最远位置 和这一块的答案 int f[MAXN][MAXM+1]; LL g[MAXN][MAXM+1]; int pw[MAXM+1]; inline LL calc(int l,int p){ if(l > p) return 0; if(l >= ::l[p]) return p-l; LL res = p-::l[p],now = 1;p = ::l[p]; ROF(i,MAXM,0){ if(f[p][i] < l) continue; res += g[p][i] + now*(p-f[p][i]); now += (1<<i); p = f[p][i]; } if(l <= p) res += (now+1)*(p-l); return res; } inline LL gcd(LL x,LL y){ return !y ? x : gcd(y,x%y); } int main(){ pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1; scanf("%d",&n); FOR(i,2,n) scanf("%d",l+i),f[i][0] = l[i]; ROF(i,n-1,2) f[i][0] = std::min(f[i][0],f[i+1][0]),g[i][0] = i-f[i][0]; f[1][0] = 0; FOR(j,1,MAXM){ FOR(i,1,n){ f[i][j] = f[f[i][j-1]][j-1]; g[i][j] = g[i][j-1]+g[f[i][j-1]][j-1]+(f[i][j-1]-f[i][j])*pw[j-1]; } } int q;scanf("%d",&q); // DEBUG(calc(3,6)); // exit(0); while(q--){ int l,r,x;scanf("%d%d%d",&l,&r,&x); LL res = calc(l,x)-calc(r+1,x); LL g = gcd(r-l+1,res); printf("%lld/%lld\n",res/g,(r-l+1)/g); } return 0; }B. Minimax设 $f_{v,i}$ 表示 $v$ 号点权值为 $i$ 的概率，考虑如何合并两个子树 $x,y$：$$ f_{v,i} = f_{x,i}(p_v\sum_{j < i} f_{y,j}+(1-p_v)\sum_{j > i} f_{y,j}) + f_{y,i}(p_v\sum_{j < i} f_{x,j}+(1-p_v)\sum_{j > i} f_{x,j}) $$这种 dp 维护可以搞个线段树合并，每次在区间 $[l,r]$ 的时候考虑同时维护一个对 $x,y$ 分别应该打什么标记，类似cdq分治那样处理左边对右边的贡献，和右边对左边的贡献即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int ha = 998244353; const int inv = 796898467; int n; std::vector<int> G[MAXN]; int a[MAXN]; int rt[MAXN],sm[MAXN*25],tag[MAXN*25],lc[MAXN*25],rc[MAXN*25],tot; inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } inline void cover(int x,int d){ // add(tag[x],d); tag[x] = 1ll*tag[x]*d%ha; sm[x] = 1ll*sm[x]*d%ha; } inline void pushdown(int x){ if(tag[x] != 1){ if(lc[x]) cover(lc[x],tag[x]); if(rc[x]) cover(rc[x],tag[x]); tag[x] = 1; } } int p,M; inline void update(int &x,int l,int r,int p){ x = ++tot;sm[x] = tag[x] = 1; if(l == r) return; int mid = (l + r) >> 1; if(p <= mid) update(lc[x],l,mid,p); else update(rc[x],mid+1,r,p); } inline int merge(int x,int y,int dx,int dy){ if(!x && !y) return 0; if(!x || !y){ cover(x|y,x?dx:dy); return x|y; } pushdown(x);pushdown(y); int lsx = sm[lc[x]],rsx = sm[rc[x]],lsy = sm[lc[y]],rsy = sm[rc[y]]; lc[x] = merge(lc[x],lc[y],(dx+1ll*(1+ha-p)%ha*rsy%ha)%ha,(dy+1ll*(1+ha-p)%ha*rsx%ha)%ha); rc[x] = merge(rc[x],rc[y],(dx+1ll*p*lsy%ha)%ha,(dy+1ll*p*lsx%ha)%ha); sm[x] = (sm[lc[x]]+sm[rc[x]])%ha; return x; } inline int query(int x,int l,int r,int p){ if(l == r) return sm[x]; int mid = (l + r) >> 1;pushdown(x); if(p <= mid) return query(lc[x],l,mid,p); return query(rc[x],mid+1,r,p); } inline void dfs(int v){ if(G[v].empty()){ update(rt[v],1,M,a[v]); return; } for(auto x:G[v]) dfs(x); if(G[v].size() == 1){ rt[v] = rt[G[v][0]]; return; } p = a[v]; rt[v] = merge(rt[G[v][0]],rt[G[v][1]],0,0); } int main(){ scanf("%d",&n); FOR(i,1,n){ int f;scanf("%d",&f); if(f) G[f].pb(i); } std::vector<int> S; FOR(i,1,n){ scanf("%d",a+i); if(G[i].empty()) S.pb(a[i]); else a[i] = 1ll*a[i]*inv%ha; } std::sort(all(S));M = S.size(); FOR(i,1,n) if(G[i].empty()) a[i] = std::lower_bound(all(S),a[i])-S.begin()+1; dfs(1); int ans = 0; FOR(i,1,M){ int t = query(1,1,M,i); // DEBUG(t); add(ans,1ll*i*S[i-1]%ha*t%ha*t%ha); } printf("%d\n",ans); return 0; }C. 随机算法考虑给定最终选出的一个独立集序列 $p_1,p_2,\ldots,p_m$，如何求有多大的概率生成的排列能得到这个序列。首先第一个数一定是 $p_1$，接下来和 $p_1$ 相连的点就可以乱放了，在剩下的点中第一个要放的一定是 $p_2$，然后和 $p_2$ 相连，还没有被放完的点也可以乱放了。所以我们处理出 $sz_S$ 表示集合 $S$ 放完之后，有多少个点可以乱放（包含集合 $S$ 内的点），并且这个只对独立集有定义。所以概率就是：$$ \prod_{i=1}^m \frac{1}{n-sz_{\cup_{j=1}^{i-1}\{p_j\}}} $$我们考虑对这个dp：设 $f_S$ 表示最终独立集序列为 $S$ ，所有 $|S|!$ 种方案的概率的和，答案显然就是每个最大独立集的 $f_S$。转移只需要枚举一个点，如果可以加入这个独立集就把对应的概率乘上就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 20; const int ha = 998244353; #define lowbit(x) ((x)&(-(x))) int n,m,e[MAXN]; int ee[(1<<MAXN)+3],sz[(1<<MAXN)+3];// 选了独立集 S 后 位置可以自由选择的位置的数量 int f[(1<<MAXN)+3];// S 内 任意顺序排列概率的和 bool vis[(1<<MAXN)+3]; int inv[MAXN+1]; inline void add(int &x,int y){ x += y-ha;x += (x>>31&ha); } int main(){ inv[1] = 1;FOR(i,2,MAXN) inv[i] = (ha-1ll*(ha/i)*inv[ha%i]%ha)%ha; scanf("%d%d",&n,&m); FOR(i,1,m){ int u,v;scanf("%d%d",&u,&v);--u;--v; e[u] |= (1<<v);e[v] |= (1<<u); } FOR(i,0,n-1) ee[1<<i] = e[i]; FOR(S,1,(1<<n)-1) ee[S] = ee[S-lowbit(S)]|ee[lowbit(S)]; int mx = 0; FOR(S,0,(1<<n)-1) if(!(ee[S]&S)) vis[S] = 1,mx = std::max(mx,(int)__builtin_popcount(S)); FOR(S,0,(1<<n)-1) sz[S] = __builtin_popcount(ee[S]|S); f[0] = 1; FOR(S,0,(1<<n)-1){ if(!f[S]) continue; if(!vis[S]) continue; FOR(i,0,n-1){ if((S>>i)&1) continue; if(!vis[S|(1<<i)]) continue; add(f[S|(1<<i)],1ll*f[S]*inv[n-sz[S]]%ha); } } int ans = 0; FOR(S,0,(1<<n)-1) if(vis[S] && __builtin_popcount(S) == mx) add(ans,f[S]); printf("%d\n",ans); return 0; }