A贪心填。先尽量填竖着的再填横着的。因为这样最多会浪费 $1$ 个，所以达到了答案的上界。求出上界判断是否 $\leq$ 即可。B枚举一个位置 $i$，前面只保留 $0$ 后面只保留 $1$，判断是否合法即可。C首先第一步横着走还是竖着走都是一样的。我们设第一步横着走。那么横着走只可能用奇数位置的 $c_i$，竖着走只可能用偶数位置的 $c_i$。枚举总共有几段，然后贪心选择最小的即可。注意要保证每个 $c_i$ 被至少选一次。D推一下式子：设 $g=\gcd(a,b)$：$$ c\frac{ab}{g}-dg = x\\ cab = gx + dg^2\\ $$设 $a' = \frac{a}{g},b' = \frac{b}{g}$：$$ ca'b' = \frac{x}{g}+d\\ a'b' = \frac{\frac{x}{g}+d}{c} $$我们枚举 $g|x$，相当于问有多少对数字 $(a',b')$，满足 $\gcd(a',b')=1$ 并且 $a'b' = x$，设 $x$ 有 $w(x)$ 个质因子，答案就是 $2^{w(x)}$。线性筛预处理 $w(x)$ 即可。复杂度 $O(n+\sqrt n)$ ，可能需要卡常。E暴力做法：枚举 $l_1,r_1$，然后以这个为开头整一个 dp：设 $f_{i,j,c}$ 表示当前考虑到位置 $s_i,t_j$ 了（这两个位置还没选），最后一次选的字符是 $c$，转移枚举下一步选哪个即可。复杂度 $O(n^4 |\Sigma|)$。复杂度瓶颈在于枚举 $l_1,r_1$，考虑把枚举这个的过程也扔到 dp 里：设 $f_{i,j,c,0/1}$ 表示考虑到位置 $s_i,t_j$，如果最后一维是 $0$，$c \in \{0,1\}$，表示当前是在枚举 $i$ 还是枚举 $j$（这里设计成先移动 $i$ 再移动 $j$ 是为了防止算枚举的方案数）；如果最后一维是 $1$ 表示当前已经选好了某个位置，$c$ 就是正常表示最后一个字母是啥了。最后枚举结束的位置把答案加起来即可。写下转移式子：对于第一种转移，有：$$ \begin{align*} f_{i,j,0,0} &\to f_{i+1,j,0,0}\\ f_{i,j,0,0} &\to f_{i,j,1,0}\\ f_{i,j,1,0} &\to f_{i,j+1,1,0}\\ f_{i,j,1,0} &\to f_{i+1,j,s[i],1}\\ f_{i,j,1,0} &\to f_{i,j+1,t[j],1} \end{align*} $$对于第二种转移，就是暴力时的转移式子，也就是：$$ \begin{align*} [c \neq s[i]]f_{i,j,c,1} &\to f_{i+1,j,s[i],1}\\ [c \neq t[j]]f_{i,j,c,1} &\to f_{i,j+1,t[j],1} \end{align*} $$不过注意到我们这样实际上只要某一个串开始选就会被计入答案了，也就是说我们会多算某一个字符串选空字符串的情况，最后减去即可。这里减去要枚举每一个区间，判断是否可行，然后减去能产生的贡献。复杂度 $O(n^2 |\Sigma|)$。空间需要稍微注意一下。F普及组树形 dp。考虑树形 dp 求直径我们会记录 $v$ 往下的最长单链的长度，这个题我们也这样搞：设 $f_{v,i}$ 表示 $v$ 子树，最长单链长度为 $i$ 的方案树，转移合并两个子树，枚举是否切割，如果不切的话， $f_{v,i} \times f_{x,j} \to f_{v,\max(i,j+1)}$，这里要求 $i+j+1 \leq k$ 即可。树形背包，两维只需要枚举到 $sz_v,sz_x$。复杂度 $O(n^2)$。转移（或许？）可以长链剖分优化，因为第二维只关于深度，转移整体平移一下，所以可以直接 $O(1)$ 继承长儿子，剩下的暴力合并打标记即可。G如果不需要修改，答案就是 $\sum_{v \in V} (\text{deg}(v) \bmod 2)$：因为我们可以构造欧拉回路，将奇点都连到一个工具点 $S$ 上，然后跑 $S$ 开始的欧拉回路，按照方向是入边还是出边来分配颜色就好了。考虑如何动态维护这个东西：一个直观的想法是根据两端点的度数奇偶性进行分类讨论，但是我们新加入的边某个端点是奇点的时候我们要依据这个端点多余的边来确定新的点的颜色，所以我们记录 $to_x$ 表示如果 $x$ 是奇点，那么 $x$ 没配对的边是哪一个；考虑现在加入边 $w=(u,v)$：如果两个端点都是偶点：那这个边给什么颜色都无所谓，不失一般性我们设这个边的颜色为 $0$；如果一个端点是奇点一个是偶点：设 $u$ 是奇点，那么 $w$ 的颜色和 $to_u$ 的应该相反，然后 $u$ 变成了偶点，$v$ 变成了奇点，所以还有 $to_v = w$；两个端点都是奇点：我们假设 $u$ 和 $v$ 不在一个联通块：首先先把 $w$ 加入 $u$ 中，发现 $w$ 的颜色和 $to_u$ 的应该相反；然后把 $w$ 加入 $v$ 中：发现这时候 $w$ 的颜色和 $to_v$ 应该相反，也就是 $to_u$ 和 $to_v$ 颜色应该相同；但是有可能不相同，解决方案是我们考虑一个联通块内反转所有颜色的边答案是不变的，所以我们把 $v$ 的联通块所有的边颜色反转即可。为了支持这些操作，我们要写一个并查集维护在同一联通块的边，每个集合维护一下 $0$ 边的哈希值和和 $1$ 边的哈希值和。支持某个集合反转可以用类似带权并查集的方法：我们让某个点 $v$ 的权值为 $v$ 到并查集根的所有点的颜色的异或，然后我们钦定并查集根的颜色为 $0$，就能支持反转了。复杂度 $O(n \alpha(n))$。注意小心维护全局答案和每个联通块的值的答案。注意细节：第三种类如果 $u,v$ 在一个连通块内不能进行反转，要不然会违反根颜色钦定为 $0$ 的性质。
A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合，转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论：对于 $\leq \sqrt n$ 的质数只有 $8$ 个，先状压，然后将其他的数字，如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人，所以对每一类先预处理 $g_{S}$ 表示那 $8$ 个质数的状态为 $S$ 的方案数，这里复杂度是 $O(n2^8)$ 的，然后再合并起来，复杂度是 $O(n3^8)$（可能是）。#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 = 500+5; const int B = 8; int n,ha; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } bool p[MAXN]; int prime[MAXN],cnt; inline void prework(){ FOR(i,2,MAXN-1){ if(!p[i]) prime[++cnt] = i; for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){ p[i*prime[j]] = 1; if(!(i%prime[j])) break; } } } int g[MAXN][(1<<B)+3],f[2][(1<<B)+3][(1<<B)+3]; int h[2][(1<<B)+3]; bool del[MAXN]; int zt[MAXN]; int main(){ prework(); scanf("%d%d",&n,&ha); FOR(i,1,B){ for(int j = prime[i];j <= n;j += prime[i]) zt[j] |= (1<<(i-1)); } FOR(i,B+1,cnt){ if(prime[i] > n) break; // printf("%d\n",prime[i]); std::vector<int> S; for(int j = prime[i];j <= n;j += prime[i]) S.pb(j),del[j] = 1; // for(auto x:S) printf("%d ",x);puts(""); int now = 0;CLR(h[now],0); h[now][0] = 1; for(auto x:S){ CLR(h[now^1],0); FOR(S,0,(1<<B)-1){ if(!h[now][S]) continue; add(h[now^1][S],h[now][S]); add(h[now^1][S|zt[x]],h[now][S]); } now ^= 1; } // DEBUG(h[now][1]); // exit(0); FOR(S,0,(1<<B)-1) g[i][S] = h[now][S]; } int now = 0;f[now][0][0] = 1; FOR(i,2,n){ if(del[i]) continue; CLR(f[now^1],0); FOR(S1,0,(1<<B)-1){ FOR(S2,0,(1<<B)-1){ if(S1&S2) continue; if(!(S2&zt[i])) add(f[now^1][S1|zt[i]][S2],f[now][S1][S2]); if(!(S1&zt[i])) add(f[now^1][S1][S2|zt[i]],f[now][S1][S2]); add(f[now^1][S1][S2],f[now][S1][S2]); } } now ^= 1; } FOR(i,B+1,cnt){ if(prime[i] > n) break; CLR(f[now^1],0); FOR(S1,0,(1<<B)-1){ FOR(S2,0,(1<<B)-1){ if(S1&S2) continue; if(!f[now][S1][S2]) continue; int S = ((1<<B)-1)^S1; for(int T = S;;T=(T-1)&S){ // assert((T&S1)==0); add(f[now^1][S1][S2|T],1ll*f[now][S1][S2]*g[i][T]%ha); if(!T) break; } S = ((1<<B)-1)^S2; for(int T = S;;T=(T-1)&S){ // assert((T&S2)==0); add(f[now^1][S1|T][S2],1ll*f[now][S1][S2]*g[i][T]%ha); if(!T) break; } add(f[now^1][S1][S2],ha-f[now][S1][S2]); } } now ^= 1; } int ans = 0; FOR(S1,0,(1<<B)-1) FOR(S2,0,(1<<B)-1) if(!(S1&S2)) add(ans,f[now][S1][S2]); printf("%d\n",ans); return 0; }B.【ZJOI 2016】线段树神仙 dp 题。。一开始就想不到。首先考虑最终的序列肯定是若干个极长区间，我们枚举 $x$ 算值 $x$ 的贡献，我们考虑每种情况的每个位置只在极长区间被算到，设 $f_{i,l,r}$ 表示考虑了 $i$ 次操作，区间 $[l,r]$ 是一段 $\leq x$ 的极长区间的方案数（也就是 $a_{l-1} > x,a_{r+1} > x$）。转移的时候考虑下一次操作 $[ll,rr]$ ，分类讨论：$[ll,rr]$ 被 $[l,r]$ 完全包含或无交：不影响这段极长区间，设这样的区间个数为 $g(l,r)$，转移 $f_{i,l,r}\times g(l,r) \to f_{i+1,l,r}$$[ll,rr]$ 覆盖了 $[l,r]$ 的左端点：转移 $f_{i,l,r}\times (l-1) \to f_{i+1,rr+1,r}$$[ll,rr]$ 覆盖了 $[l,r]$ 的右端点：转移 $f_{i,l,r} \times (n-r) \to f_{i+1,l,ll-1}$最后询问的时候设 $h_{i,j}$ 表示 $i$ 位置 $\leq j$ 的方案数，也就是 $h_{i,j} = \sum_{l \leq i \leq r} f_{j,l,r}$，设权值排序后是 $v_i$，位置 $p$ 的答案就是 $\sum_{i=1}^n (h_{p,i}-h_{p,i-1})v_i$。转移部分用差分优化可以做到总复杂度 $O(n^3q)$。首先我们可以拆贡献，我们发现考虑排名为 $x$ 的值时，每个区间 $[l,r]$ 对位置 $p$ 的贡献是 $a_x-a_{x+1}$。所以我们可以每次 dp 完 $x$ 之后答案改成 $\sum_{i=1}^n h_{p,i}(v_i-v_{i+1})$。我们发现转移其实是和枚举的 $x$ 无关，考虑是否能优化掉这个 $x$ 。发现这个 $h$ 的转移和答案的统计都是线性的，所以我们只需要将初值的 $1$ 改成 $v_i-v_{i+1}$ ，转移，就能得到所有的 $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 ha = 1e9 + 7; const int inv2 = 500000004; const int MAXN = 400+5; int n,q; int a[MAXN]; std::vector<int> S; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } int f[2][MAXN][MAXN];// 用了 i 次操作,极长区间[l,r] int row[MAXN][MAXN],col[MAXN][MAXN],g[MAXN][MAXN]; int ans[MAXN]; inline int C(int n){ return 1ll*n*(n+1)%ha*inv2%ha; } int main(){ scanf("%d%d",&n,&q); FOR(i,1,n) scanf("%d",a+i),S.pb(a[i]); std::sort(all(S));S.erase(std::unique(all(S)),S.end()); FOR(i,1,n) a[i] = std::lower_bound(all(S),a[i])-S.begin()+1; int now = 0; FOR(mx,1,(int)S.size()){ std::vector<int> ps;ps.pb(0); int gx = S[mx-1];if(mx != (int)S.size()) add(gx,ha-S[mx]); FOR(i,1,n) if(a[i] > mx) ps.pb(i); ps.pb(n+1); FOR(i,1,(int)ps.size()-1){ int l = ps[i-1]+1,r = ps[i]-1; if(l <= r) add(f[now][l][r],gx); } } FOR(l,1,n) FOR(r,l,n) g[l][r] = ((C(l-1)+C(r-l+1))%ha+C(n-r))%ha; FOR(ccc,1,q){ CLR(f[now^1],0); CLR(row,0);CLR(col,0); FOR(l,1,n){ FOR(r,l,n){ if(!f[now][l][r]) continue; add(f[now^1][l][r],1ll*f[now][l][r]*g[l][r]%ha); int gx = 1ll*f[now][l][r]*(n-r)%ha; // FOR(k,1,r-1) add(f[now^1][l][k],gx); add(row[l][1],gx);add(row[l][r],ha-gx); gx = 1ll*f[now][l][r]*(l-1)%ha; // FOR(k,l+1,n) add(f[now^1][k][r],gx); add(col[r][l+1],gx);add(col[r][n+1],ha-gx); } } FOR(i,1,n) FOR(j,1,n+1) add(row[i][j],row[i][j-1]),add(col[i][j],col[i][j-1]); now ^= 1; FOR(l,1,n) FOR(r,l,n) add(f[now][l][r],row[l][r]),add(f[now][l][r],col[r][l]); } FOR(l,1,n){ FOR(r,l,n){ add(ans[l],f[now][l][r]); add(ans[r+1],ha-f[now][l][r]); } } FOR(i,1,n) add(ans[i],ans[i-1]),printf("%d%c",ans[i]," \n"[i==n]); return 0; }C. Alice和Bob又在玩游戏这是个套路题。。首先不同连通块相当于若干个子游戏，也就是 $SG$ 值的异或。我们考虑一个连通块的怎么求。我们设 $i$ 的子树的的 $SG$ 值为 $sg_i$，每次枚举一个点，删掉这些点后就变成了若干个连通块，也就是若干个子问题，对所有的分支可能都取 $\text{mex}$，设 $son_v$ 表示 $v$ 子树内的点的集合，$anc(v)$ 表示 $v$ 到当前子树的根的点的集合，可以得到转移：$$ sg_i = \text{mex}_{v \in son}\{ \text{XOR}_{x \in anc(v),y \in son_x} sg_y \} $$记 $s_v = \text{XOR}_{x \in anc(v),y \in son_x} sg_y $，我们观察一下每次子树往上合并的时候的变化：相当于每个子树内的点异或上了除了这个子树对应的儿子的其他的儿子的 $sg$ 值的异或和。相当于要支持查询一个集合的 $\text{mex}$ ，整体 $\text{XOR}$ 一个值，合并。和 $\text{XOR}$ 这种问题有关我们想到了 trie。求 $\text{mex}$ 类似线段树二分，记录一个 $sz$ 表示子树内的点的大小就可以了。合并类似线段树合并，$\text{XOR}$ 直接打标记。对 01trie 还不是很熟练调了很长时间。。回来多写点这样的题吧#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 MAXM = 16; const int M = 2e6 + 5; int n,m; struct Edge{ int to,nxt; }e[MAXN<<1]; int head[MAXN],cnt; inline void add(int u,int v){ e[++cnt] = (Edge){v,head[u]};head[u] = cnt; e[++cnt] = (Edge){u,head[v]};head[v] = cnt; } // 支持插入 合并 整体xor 求mex int tag[M],rt[MAXN],ch[M][2],tot,dep[M],sz[M]; #define lc (ch[x][0]) #define rc (ch[x][1]) inline void pushdown(int x){ if(tag[x]){ if(lc) tag[lc] ^= tag[x]; if(rc) tag[rc] ^= tag[x]; if((tag[x]>>dep[x])&1) std::swap(lc,rc); tag[x] = 0; } } inline void insert(int o,int val){ if(!rt[o]) rt[o] = ++tot; int x = rt[o];dep[x] = MAXM; ROF(i,MAXM,0){ int c = (val>>i)&1; pushdown(x); if(!ch[x][c]) ch[x][c] = ++tot,dep[tot] = i-1; x = ch[x][c]; } if(!sz[x]){ x = rt[o]; ROF(i,MAXM,0){ int c = (val>>i)&1; pushdown(x); sz[x]++; x = ch[x][c]; } sz[x]++; } } inline int query(int x){ if(!x || dep[x] == -1) return 0; pushdown(x); // DEBUG(x);DEBUG(dep[x]); if(sz[lc] < (1<<(dep[x]))) return query(lc); else return (1<<dep[x])|query(rc); } bool flag = 0; inline int merge(int x,int y){ if(!x || !y) return x+y; pushdown(x);pushdown(y); lc = merge(lc,ch[y][0]); rc = merge(rc,ch[y][1]); if(dep[x] != -1) sz[x] = sz[lc]+sz[rc]; // if(flag){ // DEBUG(x); // DEBUG(lc);DEBUG(rc); // } return x; } int sg[MAXN]; bool vis[MAXN]; inline void print(int x,int num=0){ if(dep[x] == -1){ DEBUG(num); // printf("%d\n",num); return; } pushdown(x); if(lc) print(lc,num); if(rc) print(rc,num|(1<<dep[x])); } inline void dfs(int v,int fa=0){ vis[v] = 1;int sm = 0; for(int i = head[v];i;i = e[i].nxt){ if(e[i].to == fa) continue; dfs(e[i].to,v); sm ^= sg[e[i].to]; } // if(v == 19)flag = 1; for(int i = head[v];i;i = e[i].nxt){ if(e[i].to == fa) continue; tag[rt[e[i].to]] ^= sm^sg[e[i].to]; // if(v == 19){ // DEBUG(sz[38]); // print(rt[e[i].to]); // DEBUG(rt[v]); // } rt[v] = merge(rt[v],rt[e[i].to]); } // if(v == 19) flag = 0; insert(v,sm); // if(v == 17){ // DEBUG(query(rt[v])); // DEBUG(sz[v]); // DEBUG(sz[rt[v]]); // DEBUG(rt[v]); // print(rt[v]); // } // if(v == 19){ // DEBUG(query(rt[v])); // DEBUG(sz[v]); // } sg[v] = query(rt[v]); // if(v == 19){ // DEBUG(sg[v]); // } } inline void Solve(){ scanf("%d%d",&n,&m); FOR(i,1,m){ int u,v;scanf("%d%d",&u,&v); add(u,v); } int SG = 0; // dfs(1); // FOR(i,1,n) DEBUG(sg[i]); // exit(0); FOR(i,1,n) if(!vis[i]) dfs(i),SG ^= sg[i]; // FOR(i,1,n) DEBUG(sg[i]); // DEBUG(SG); puts(SG?"Alice":"Bob"); cnt = 0;FOR(i,1,n) head[i] = 0; FOR(i,1,tot) tag[i] = ch[i][0] = ch[i][1] = dep[i] = sz[i] = 0; FOR(i,1,n) rt[i] = 0,vis[i] = 0;tot = 0; // exit(0); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }
因为某些原因晚了半小时打，然后就疯狂挂题，从前二（或许？）挂到了倒一A可以考虑哈希。这里可以给每个值随机一个哈希值，合并操作定义为异或。考试的时候写的N模好像 T 飞了。。事实上这个数据一模数就能过#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 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; } const int MAXN = 3e5 + 5; const int H = 2; const int mod[] = {0,998244353,(int)1e9+7,(int)1e9+9,666623333,1004535809}; const int MAXM = 17; std::mt19937 g(time(NULL)); inline int qpow(int a,int n,int ha){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } struct Node{ int t[H+1]; Node(){FOR(i,1,H) t[i] = 1;} inline void gen(int id){ //FOR(i,1,H) t[i] = id;//g()%mod[i]; FOR(i,1,H) t[i] = g()%mod[i]; } inline Node operator + (const Node &x) const { Node res; FOR(i,1,H) res.t[i] = 1ll*t[i]*x.t[i]%mod[i]; return res; } inline Node inv(){ Node res; FOR(i,1,H) res.t[i] = qpow(t[i],mod[i]-2,mod[i]); return res; } inline bool operator == (const Node &x) const { FOR(i,1,H) if(x.t[i] != t[i]) return 0; return 1; } inline void debug(){ FOR(i,1,H) printf("%d ",t[i]);puts(""); } }val[MAXN],chk[MAXN],ival[MAXN]; int M; struct BIT{ #define lowbit(x) ((x)&(-(x))) Node tree[MAXN]; inline void add(int pos,Node x){ while(pos <= M){ tree[pos] = tree[pos]+x; pos += lowbit(pos); } } inline Node query(int pos){ Node res; while(pos){ res = res+tree[pos]; pos -= lowbit(pos); } return res; } }bit; std::vector<int> G[MAXN]; int a[MAXN],n,q; int dfn[MAXN],sz[MAXN],dep[MAXN]; int f[MAXN][MAXM+1],ts; Node sm[MAXN]; inline void dfs(int v,int fa=0){ sm[v] = sm[fa]+val[a[v]]; sz[v] = 1;f[v][0] = fa; dfn[v] = ++ts;dep[v] = dep[fa]+1; FOR(i,1,MAXM) f[v][i] = f[f[v][i-1]][i-1]; for(auto x:G[v]){ if(x == fa) continue; dfs(x,v);sz[v] += sz[x]; } } inline int lca(int x,int y){ if(dep[x] != dep[y]){ if(dep[x] < dep[y]) std::swap(x,y); int d = dep[x]-dep[y]; FOR(i,0,MAXM) if((d>>i)&1) x = f[x][i]; } if(x == y) return x; ROF(i,MAXM,0){ if(f[x][i] == f[y][i]) continue; x = f[x][i],y = f[y][i]; } return f[x][0]; } inline Node query(int x){// 查询x->1 if(x == 0) return Node(); return sm[x]+bit.query(dfn[x]); } inline void Solve(){ ts = 0; read(n);read(q); // n = q = 100000; M = n+5; // FOR(i,1,n) a[i] = 1+g()%n; FOR(i,1,n) read(a[i]); FOR(i,2,n){ int u,v; // u = i;v = 1+g()%(i-1); read(u);read(v); // scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } FOR(i,1,n) val[i].gen(i),ival[i] = val[i].inv(); FOR(i,1,n) chk[i] = chk[i-1]+val[i]; dfs(1); FOR(i,1,q){ int opt,x,y; // opt = 1+g()%2; // x = 1+g()%n;y = 1+g()%n; read(opt);read(x);read(y); // scanf("%d%d%d",&opt,&x,&y); if(opt == 1){ int l = lca(x,y); Node res = query(x)+query(y); Node i = query(f[l][0]).inv(); res = res+i;res = res+i; res = res+ival[a[l]]; int len = dep[x]+dep[y]-2*dep[l]+1; puts(res==chk[len]?"Yes":"No"); } else{ int l = dfn[x],r = dfn[x]+sz[x]-1; bit.add(l,ival[a[x]]); bit.add(r+1,val[a[x]]); a[x] = y; bit.add(l,val[a[x]]); bit.add(r+1,ival[a[x]]); } } FOR(i,1,n) G[i].clear(); FOR(i,0,M) bit.tree[i] = Node(); } int main(){ int T;read(T); while(T--) Solve(); return 0; }Bsb题，但是因为没时间了所以没有仔细思考。我们先不管 $T_i$ 的限制看看怎么做：显然是要建分层图，我们只需要建出对应的地面的点，单车的点，车站的点，地铁的点，对题意模拟建图即可。发现这个 $T_i$ 的限制形如限制某条边如果只能在 $\bmod T_i = x_i$ 的时间通过。首先贪心地想我们肯定不会战略停留一会儿在走，所以我们还是跑最短路，对有这种特殊限制的边，额外计算等待时间即可。（我猜这个只能跑 dij）注意 $T_i$ 是没有限制 $\leq 10^9$ 的，相关变量要开 long long。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<LL,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; struct Edge{ int to;LL w;int nxt;LL T,ts; }e[MAXN<<1]; int head[MAXN],cnt; inline void add(int u,int v,LL w,LL T=0,LL ts=0){ e[++cnt] = (Edge){v,w,head[u],T,ts};head[u] = cnt; } LL dis[MAXN]; bool used[MAXN]; int N; int G[MAXN],B[MAXN],S[MAXN],T[MAXN]; inline void dij(){ std::priority_queue<P,std::vector ,std::greater > q; FOR(i,0,N) dis[i] = 1e18; q.push(MP(dis[G[1]]=0,G[1])); while(!q.empty()){ int v = q.top().se;LL d = q.top().fi;q.pop(); if(d != dis[v]) continue; if(used[v]) continue; used[v] = 1; for(int i = head[v];i;i = e[i].nxt){ LL gx = dis[v]+e[i].w; if(e[i].T){ // DEBUG(dis[v]);DEBUG(e[i].ts);DEBUG(e[i].T); // DEBUG((e[i].ts-dis[v]%e[i].T+e[i].T)%e[i].T); gx += (e[i].ts+e[i].T-dis[v]%e[i].T)%e[i].T; } if(dis[e[i].to] > gx){ dis[e[i].to] = gx; q.push(MP(dis[e[i].to],e[i].to)); } } } } int n,r,s,x; int ee[MAXN],c[MAXN]; /* G: 地面 B: 共享单车 S: 车站 T: 地铁 */ int v[MAXN],l[MAXN]; signed main(){ scanf("%d%d%d%d",&n,&r,&s,&x); FOR(i,1,n) scanf("%d",ee+i); FOR(i,1,n) scanf("%d",c+i); FOR(i,1,n) G[i] = ++N,B[i] = ++N,S[i] = ++N; FOR(i,1,n) add(G[i],B[i],x),add(B[i],G[i],0); FOR(i,1,n) add(G[i],S[i],ee[i]);//,add(S[i],G[i],ee[i]); FOR(i,1,r){ int u,v,w;scanf("%d%d%d",&u,&v,&w); add(B[u],B[v],w);add(B[v],B[u],w); } FOR(iii,1,s){ int k;scanf("%d",&k); FOR(i,1,k) scanf("%d%d",v+i,l+i);scanf("%d",v+k+1); LL tt;scanf("%lld",&tt); FOR(i,1,k) T[v[i]] = ++N; if(v[k+1] != v[1]) T[v[k+1]] = ++N; LL sm = 0; FOR(i,1,k){ add(T[v[i]],T[v[i+1]],l[i],tt,sm); (sm += l[i]) %= tt; } if(v[1] == v[k+1]) sm = 0; ROF(i,k,1){ add(T[v[i+1]],T[v[i]],l[i],tt,sm); (sm += l[i]) %= tt; } FOR(i,1,k) add(S[v[i]],T[v[i]],0),add(T[v[i]],S[v[i]],c[v[i]]),add(T[v[i]],G[v[i]],ee[v[i]]); if(v[k+1] != v[1]) add(S[v[k+1]],T[v[k+1]],0),add(T[v[k+1]],S[v[k+1]],c[v[k+1]]),add(T[v[k+1]],G[v[k+1]],ee[v[k+1]]); } dij(); FOR(i,1,n) printf("%lld ",dis[G[i]]);puts(""); return 0; }C是个神仙剪枝题。首先暴力是一分没有的。这个问题有一个经典剪枝是每次选尽可能大的一些数，如果还是不能大于原数就返回；选尽可能小的数，如果大于原数也返回。这样就能获得 $10$ 分了。一个很 naive 的想法是求个逆元然后做背包：但是发现这样会犯单面错误：它会统计所有合法的方案，但是也会错误统计部分不合法方案。所以我们可以在每一层用这个背包来判断是否有往下搜索的必要，就可以拿到 $50$ 分的好成绩了。（搜索剪枝优化的时候要考虑一些单面错误的东西。。）神仙正解：我们先倒着考虑，将目标消成 $0$。首先我们发现直接对通分后的值域做背包是对的，但是值域过大。于是我们考虑只取 $\leq \sqrt n$ 的所有数的 $\text{lcm}$（大概是 $2^3 \times 3^2 \times 5 \times 7 = 2520$，对所有能被通分成这个数的数都拿出来做背包。然后剩下的数都是存在且仅存在一个 $> \sqrt n$ 的因数 $p^c$。首先我们发现 $>\sqrt n$ 的质数不能要（消不掉），所以我们考虑所有这样的因数，只有 $\{11,13,16,17,19,23,25,27,29,31,37\}$。我们将剩下的所有数按照是某个数的倍数分类，对每一类内部先搜出所有方案，然后考虑 dfs。这里有一个很好的剪枝是发现如果我们考虑完了 $p^c$ 后分母如果还是 $p^c$ 的倍数，那么这个方案一定不合法（因为消不掉），所以加上这个剪枝后跑的飞快（我的程序极限数据 70ms）那么这个剪枝为什么是对的呢？首先我们注意到 $(a,b) = 1\Rightarrow (a+b,ab)=1$证明：$$ \begin{aligned} (a+b,ab) &= (a+b,ab-a(a+b))\\ &= (a+b,a^2)\\ \text{又} &(a,b) = (a,a+b) = 1\\ \therefore (a+b,a^2) &= 1 \end{aligned} $$我们考虑如果一个埃及分数加上后能消掉分母的一些东西那么一定满足加上后能约分，设这个算式是 $\frac{a}{b}+\frac{1}{c}$，能否约分取决于 $(bc,ac+b)$。如果做完了 $p^c$ 的所有倍数后，将 $\frac{a}{b}$ 裂出来分母仅包含 $p^c$ ，可以得到 $(b,c)=1$，注意到 $(a,b)=1$，所以$$ \begin{aligned} (bc,ac+b) &= (b,ac+b)\times (c,ac+b) \\ &= (b,ac) \times (c,b)\\ &= 1 \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 B = 2520; const int MAXN = 30+5; inline LL gcd(LL x,LL y){ return !y ? x : gcd(y,x%y); } struct Node{ LL x,y;// y/x Node(LL y=0,LL x=0) : x(x),y(y) {} inline Node operator + (const Node &t) const { LL g = gcd(x*t.x,y*t.x+x*t.y); return Node((y*t.x+x*t.y)/g,x*t.x/g); } inline Node operator - (const Node &t) const { LL g = gcd(x*t.x,y*t.x-x*t.y); return Node((y*t.x-x*t.y)/g,x*t.x/g); } inline bool operator < (const Node &t) const { return y*t.x < x*t.y; } }; LL f[MAXN][2*B+3]; // 选了i个,答案在分母是B的情况下是j const int p[] = {0,11,13,16,17,19,23,25,27,29,31,37}; std::vector<int> G[MAXN]; std::vector<std::pair<Node,int> > ways[MAXN]; LL ans = 0; int tot = 11,m,n; Node req; inline void work(int id){ if(G[id].empty()) return; int sz = G[id].size(); FOR(S,1,(1<<sz)-1){ Node res(0,1); FOR(i,0,sz-1){ if((S>>i)&1){ res = res+Node(1,G[id][i]); } } if(req < res) continue; if(!((res-req).x%p[id])) continue; ways[id].pb(MP(res,__builtin_popcount(S))); } } // y/x inline void dfs(int dep,Node num,int cnt){ if(cnt > m) return; if(cnt == m){ if(num.y == 0) ans++; return; } if(dep == tot+1){ if(B%num.x) return; int v = num.y*(B/num.x); ans += f[m-cnt][v]; return; } dfs(dep+1,num,cnt); for(auto x:ways[dep]){ if(num < x.fi) continue; Node nxt = num-x.fi; // if(!(nxt.x%p[dep])) continue; dfs(dep+1,nxt,cnt+x.se); } } int main(){ int x,y;scanf("%d%d%d%d",&m,&n,&x,&y); int g = gcd(x,y); x /= g;y /= g;req = Node(x,y); f[0][0] = 1; FOR(x,1,n){ if(B%x) continue; int v = B/x; // DEBUG(v); // f[i][j] = f[i-1][j-v] ROF(i,m,1){ ROF(j,2*B,v){ f[i][j] += f[i-1][j-v]; } } } FOR(x,1,n){ if(!(B%x)) continue; bool flag =0; FOR(i,1,tot){ if(!(x%p[i])){ G[i].pb(x);flag=1; break; } } } FOR(i,1,tot) work(i); dfs(1,req,0); printf("%lld\n",ans); return 0; }
A如果长度为 $2$ 特判，否则将第一个数和剩下的数分开。B$B$ 进制下正整数的数根等价于 $\pmod {B-1}$，注意这里 $0$ 对应的答案是 $B-1$。所以答案是 $(k-1)B+x$。C双指针扫出所有相同的段，每段取前 $k$ 大即可。D观察一下发现只需要枚举 $x|n$，然后前缀和预处理+判断所有矩阵是不是全 $0/1$ 矩阵即可。时间复杂度分析一波：先考虑行的贡献，枚举的每一个 $x|n$ 都会贡献 $\frac{n}{x}$ ，那么相当于是 $\sigma_1(n)$，所以复杂度是 $O(\sigma_1(n)^2)$。这是可以分析出复杂度 $O(n^2)$ 的：考虑将 $n$ 的所有因子分类，对于 $>\sqrt{n}$ 的，只有 $O(1)$ 个，所以复杂度贡献 $O(n)$；对于 $<\sqrt{n}$ 的，因为 $\sqrt{n} \times \sqrt{n} = n$，所以他们的和顶多贡献总复杂度 $O(n)$，所以 $\sigma_1(n)$ 的量级可以认为是 $O(n)$ 的。E这种区间 dp 模型都没见过。。再看了两道CF 1132 F题目链接每次删除相同的连续段有一个性质：互不包含的删除可以任意调换相对顺序。所以我们对于一个区间可以钦定左端点是最后被删除的。这个题就可以设 $f_{l,r}$ 表示删除区间 $[l,r]$ 的代价，转移首先可以花 $1$ 代价删除 $l$，或者是枚举一个 $x$，满足 $s_l = s_x$，将 $l$ 并入 $x$，代价就是 $f_{l+1,x-1}+f_{x,r}$。#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 = 500+5; int f[MAXN][MAXN],n; char str[MAXN]; // 删除操作 一定互相包含 不交的连通块顺序无关 // 删除首先枚举 mid,那么如果str[l]==str[mid]先删除[l+1,mid-1]然后l和mid就并起来了 int main(){ scanf("%d",&n); scanf("%s",str+1); CLR(f,0x3f); FOR(i,1,n) f[i][i] = 1,f[i][i-1] = 0; FOR(len,2,n){ FOR(l,1,n-len+1){ int r = l+len-1; f[l][r] = std::min(f[l+1][r],f[l][r-1])+1; FOR(k,l+1,r){ if(str[k] == str[l]){ f[l][r] = std::min(f[l][r],f[l+1][k-1]+f[k][r]); } } } } printf("%d\n",f[1][n]); return 0; }SPOJ ZUMA题目链接这个题我们需要知道连续段的长度了，还是用左端点最后删除的思路，设 $f_{l,r,k}$ 表示区间 $[l,r]$，$l$ 前面删除导致接了 $k$ 个和 $s_l$ 相同的数的答案。转移的时候首先可以加一个数在左端点左边，$f_{l,r,k} = f_{l,r,k+1}+1$，然后如果现在可以消除了（也就是 $k-1 == K$），那就可以消除，也就是 $f_{l,r,K} = f_{l+1,r,0}$。然后就是枚举和位置 $x$ 拼在一起，$f_{l,r,k} = f_{l+1,x-1,0}+f_{x,r,\min\{k+1,K-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 = 100+5; int n,K,a[MAXN]; int f[MAXN][MAXN][6]; inline void upmin(int &x,int y){ if(x > y) x = y; } int main(){ scanf("%d%d",&n,&K); FOR(i,1,n) scanf("%d",a+i); CLR(f,0x3f); FOR(i,1,n) FOR(j,0,K-1) f[i][i][j] = K-j-1; FOR(i,1,n) f[i][i-1][0] = 0; FOR(len,2,n){ FOR(l,1,n-len+1){ int r = l+len-1; ROF(k,K-1,0){ upmin(f[l][r][k],f[l][r][std::min(K-1,k+1)]+1); if(k == K-1) upmin(f[l][r][k],f[l+1][r][0]); FOR(x,l+1,r){ if(a[l] == a[x]) upmin(f[l][r][k],f[l+1][x-1][0]+f[x][r][std::min(K-1,k+1)]); } } } } printf("%d\n",f[1][n][0]); return 0; } /* 每次消除连续段的 如果要保留连续段消息 就要设f[i][j][k] 表示区间[i,j],i前面接了长度为k的一段和i相同的还未删除的数的方案数 然后枚举消去 转移 首先可以加入一个: f[i][j][k] = f[i][j][k+1]+1 然后可以消去k个: f[i][j][k] = f[i+1][j][0] 然后可以和后面的合并(如果相等): f[i][j][k] = f[i+1][j][k+1] */CF 1107 E首先我们先求出 $g_i$ 表示将长度为 $i$ 的区间消光的答案，这个可以用背包解决。然后，我们这个题也是要知道长度才能计算贡献，所以设 $f_{l,r,k}$ 表示 $[l,r]$ 前面跟着长度 $k$ 的答案，转移的时候可以先删掉这一段，$f_{l,r,k} = f_{l+1,r,0}+g_{k+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 = 100+5; int n; char str[MAXN]; LL a[MAXN];int b[MAXN]; LL f[MAXN][MAXN][MAXN];// 区间[l,r],l接了长度为k的一段 inline void upmax(LL &x,LL y){ if(x < y) x = y; } int main(){ scanf("%d",&n); scanf("%s",str+1); FOR(i,1,n) scanf("%lld",b+i); FOR(i,1,n){ FOR(j,0,i-1){ upmax(a[i],a[j]+b[i-j]); } } CLR(f,~0x3f); FOR(i,1,n){ FOR(j,0,n-1) f[i][i][j] = a[j+1]; f[i][i-1][0] = 0; } FOR(len,2,n){ FOR(l,1,n-len+1){ int r = l+len-1; FOR(k,0,n){ upmax(f[l][r][k],f[l+1][r][0]+a[k+1]); FOR(x,l+1,r){ if(str[x] == str[l]) upmax(f[l][r][k],f[l+1][x-1][0]+f[x][r][k+1]); } } } } printf("%lld\n",f[1][n][0]); return 0; } /* 区间连续段+删除相关dp可以记左端点前面的个数 转移 枚举一个str[l]==str[x] f[l][r][k] = f[l+1][x-1][0]+f[x][r][k+1] f[l][r][k] = f[l][r][0]+a[k+1] */总结：区间 dp 如果有时候可以不注意操作顺序，就可以定义最有利于转移的顺序（这种模型中就是最后删除左端点），然后记录与其相关的值（最左边延长了多少）。这种删除模型的核心是删掉了后会接起来，所以记录端点往左延伸多少也没错。另一个区间dp：每次可以选择一段区间染色，求最少到目标状态的步数。先考虑染色操作有时候不能分成两个区间的原因是可能会跨段染色，于是我们可以设 $f_{l,r}$ 表示 $[l,r]$ 的答案，每次转移的时候如果 $c_l = c_r$ 那么我们可以用 $f_{l+1,r}$ 染完之后顺便把 $l$ 染了，也就是 $f_{l,r}$ 可以用 $f_{l+1,r},f_{l,r-1}$ 更新。如果不相等，说明这两个点属于两次不同的染色，然后就可以枚举断点更新了。F直接正着做不太好处理每个位置前面对自己的贡献（状态会爆炸），我们倒着做，反而考虑每个位置对别人的贡献。首先贷款肯定是紧密连接的（要不然不优）。设 $f_{i,j}$ 表示考虑到第 $i$ 个贷款，当前选了 $j$ 个的方案数，转移首先可以不选这个点，$f_{i,j} \to f_{i+1,j}$，或者可以选这个点，$f_{i,j} \to f_{i+1,j+1}+a_i-b_i\times\min(k_i,j)$。但是发现这样 dp 的顺序不对，按照我们的方法我们应该贪心地让 $b_i$ 大的先被考虑。但是发现还是不对（这样写你应该会发现第二个样例答案少了 $1$），发现原因是有些小的数已经覆盖了超过最右边的点，所以可以将这个点往前拿减少这个点的贡献，并且后面的点由于没有覆盖超，贡献是不变的。这种情况我们直接把后面的点全都一直往后拿就行，具体要加个转移 $f_{i,j} \to f_{i+1,j} + a_i-b_ik_i$。#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 = 500+5; struct Node{ LL a,b,k; inline bool operator < (const Node &t) const { return b > t.b; } }v[MAXN]; int n; LL f[MAXN][MAXN]; // i 个,选了j个 int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%lld%lld%lld",&v[i].a,&v[i].b,&v[i].k); std::sort(v+1,v+n+1); CLR(f,-0x3f); f[0][0] = 0; FOR(i,1,n){ FOR(j,0,i){ f[i][j] = f[i-1][j]; f[i][j] = std::max(f[i][j],f[i-1][j]+v[i].a-v[i].k*v[i].b); if(j-1 >= 0) f[i][j] = std::max(f[i][j],f[i-1][j-1]+v[i].a-std::min((LL)(j-1),v[i].k)*v[i].b); } // DEBUG(f[i][0]); } LL ans = -1e18; FOR(i,0,n) ans = std::max(ans,f[n][i]); printf("%lld\n",ans); return 0; }G感觉难度倒序啊。。。这个题首先枚举右端点，然后考虑计算所有左端点的答案，发现那个 $\max$ 固定 $r$ 后是个后缀和的形式，所以用单调栈维护一下所有后缀最大值，算一下贡献插入 multiset ，没了。如果想做到 $O(n)$ 的话，首先 ST 表那一部分可以用每次暴力扫，删除栈顶的时候直接获得栈顶的最小值贡献来优化掉。multiset 那一部分其实可以对栈记录一个前缀最小值，这样每次更新就好了。（主要还是为了 vp 的时候避免细节快点写用了 $\log$）#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; struct Node{ LL val,ps,gx; Node(LL val=0,LL ps=0,LL gx=0) : val(val),ps(ps),gx(gx) {} }; int n,a; int d[MAXN]; LL c[MAXN]; Node st[MAXN]; int tp; LL mn[MAXM+1][MAXN];// 求最小值 int pc[MAXN]; inline LL calc(int l,int r){ int c = pc[r-l+1]; l = std::max(l,0);r = std::min(r,n); return std::min(mn[c][l],mn[c][r-(1<<c)+1]); } std::multiset<LL> S; int main(){ pc[0] = -1;FOR(i,1,MAXN-1) pc[i] = pc[i>>1]+1; scanf("%d%d",&n,&a); FOR(i,1,n) scanf("%d%lld",d+i,c+i); FOR(i,1,n) c[i] = a-c[i],c[i] += c[i-1]; FOR(i,1,n) mn[0][i] = c[i]; FOR(i,1,MAXM){ for(int j = 0;j+(1<<(i-1)) < MAXN;++j){ mn[i][j] = std::min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]); } } LL ans = 0; FOR(r,1,n){ ans = std::max(ans,c[r]-c[r-1]); if(r != 1){ LL now = 1ll*(d[r]-d[r-1])*(d[r]-d[r-1]); while(tp && st[tp].val <= now){ S.erase(S.find(st[tp].gx)); tp--; } st[tp+1] = Node(now,r,calc(st[tp].ps-1,r-1)+now); ++tp;S.insert(st[tp].gx); } if(!S.empty()) ans = std::max(ans,c[r]-*S.begin()); } printf("%lld\n",ans); return 0; }
A假设 $a \geq b$$$ \begin{aligned} \gcd(q^a-q,q^b-1) &= \gcd(q^b-1,q^a-q^b)\\ &= \gcd(q^b-1,q^b(q^{a-b}-1))\\ &= \gcd(q^b-1,q^{a-b}-1) \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 int q,a,b,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; } inline int gcd(int a,int b){ if(a < b) return gcd(b,a); if(!b) return (qpow(q,a)+ha-1)%ha; return gcd(b,a%b); } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&q,&a,&b,&ha); LL x = qpow(q,a)-1,y = qpow(q,b)-1; printf("%d\n",gcd(a,b)); } return 0; }B开 1e6 个 vector 存一下所有的倍数，每次取出最少的，如果数量变成 $0$ 了就弹掉。复杂度 $O(n \log 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; 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; } bool p[MAXN]; int prime[MAXN],tot,d[MAXN]; inline void prework(){ FOR(i,2,MAXN-1){ if(!p[i]) prime[++tot] = i,d[i] = i; for(int j = 1;j <= tot && 1ll*i*prime[j] < MAXN;++j){ p[i*prime[j]] = 1;d[i*prime[j]] = prime[j]; if(!(i%prime[j])){ d[i*prime[j]] = d[i]; break; } } } } int a[MAXN],n,m,cnt[MAXN]; std::vector<int> dec[MAXN]; int pp[MAXN],ee[MAXN],sz; inline void dfs(int dep,int id,int sm=1){ if(dep == sz+1){ dec[id].pb(sm); return; } dfs(dep+1,id,sm); FOR(i,1,ee[dep]) sm *= pp[dep],dfs(dep+1,id,sm); } inline void fj(int i){ if(i == 1){ dec[1].pb(1); return; } int x = i,las = d[x];x /= d[x]; sz = 0;int cnt = 1; while(x != 1){ if(las != d[x]){ ++sz; pp[sz] = las; ee[sz] = cnt; las = d[x];cnt = 0; } x /= d[x];cnt++; } ++sz;pp[sz] = las;ee[sz] = cnt; dfs(1,i); } std::vector<int> G[MAXN]; int main(){ prework(); read(n); FOR(i,1,n) read(a[i]),++cnt[a[i]]; ROF(i,MAXN-1,1){ if(cnt[i]){ fj(i); for(auto x:dec[i]) G[x].pb(i); } } read(m);std::vector<int> ans; FOR(i,1,m){ int x;read(x); while(!G[x].empty() && !cnt[G[x].back()]) G[x].pop_back(); if(G[x].empty()) break; int v = G[x].back(); ans.pb(v);cnt[v]--; } printf("%d\n",(int)ans.size()); for(auto x:ans) printf("%d ",x);puts(""); return 0; }C拆式子：$$ \begin{aligned} &\sum_{i=1}^n \sum_{j=i+1}^n A_i^2B_j^2+A_j^2B_i^2-A_iA_jB_iB_j\\ &= (\sum_{i=1}^n A_i^2)(\sum_{j=1}^n B_j^2) - (\sum_{i=1}^n A_iB_i)^2\\ \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 = 5e5 + 5; const int ha = 998244353; const int inv2 = 499122177; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } int a[MAXN],b[MAXN]; 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 BIT{ #define lowbit(x) ((x)&(-(x))) int tree[MAXN]; inline void add(int pos,int x){ while(pos < MAXN){ ::add(tree[pos],x); pos += lowbit(pos); } } inline int calc(int pos){ if(!pos) return 0; int res = 0; while(pos){ ::add(res,tree[pos]); pos -= lowbit(pos); } return res; } inline int query(int l,int r){ return (calc(r)+ha-calc(l-1))%ha; } }bit1,bit2,bit3; int n,q; int main(){ read(n);read(q); FOR(i,1,n) read(a[i]),bit1.add(i,1ll*a[i]*a[i]%ha); FOR(i,1,n) read(b[i]),bit2.add(i,1ll*b[i]*b[i]%ha); FOR(i,1,n) bit3.add(i,1ll*a[i]*b[i]%ha); FOR(i,1,q){ int opt;read(opt); if(opt == 1){ int l,r;read(l);read(r); int a = bit1.query(l,r),b = bit2.query(l,r),c = bit3.query(l,r); int res = (1ll*a*b%ha+ha-1ll*c*c%ha)%ha; printf("%d\n",res); } else{ int p;read(p); bit1.add(p,ha-1ll*a[p]*a[p]%ha); bit2.add(p,ha-1ll*b[p]*b[p]%ha); bit3.add(p,ha-1ll*a[p]*b[p]%ha); read(a[p]);read(b[p]); bit1.add(p,1ll*a[p]*a[p]%ha); bit2.add(p,1ll*b[p]*b[p]%ha); bit3.add(p,1ll*a[p]*b[p]%ha); } } return 0; }D这个题循环是假的，实际是给定了一些不等式关系，要求你确定有多少组解。我们只关心相对大小关系；如果相对大小关系不同方案绝对不同，相对大小关系也决定了有多少组数是相等的。所以设 $f_{i,S}$ 表示从小到大选出了 $i$ 组，已经用了 $S$ 内的数的方案数，每次枚举一个子集，要满足 $S$ 内的数都不能大于这个子集内的数，转移即可。然后就可以用组合数计算答案了。这里注意到 $m$ 很小，可以手动约分。（居然之前没注意过）加强复杂度可以做到 $O(n^2 \cdot 2^n)$。做法是我们首先缩点，发现一个 SCC 内的点一定同时选，于是图变成了 DAG ，选择方案合法当且仅当当前选出的集合没有指向之前集合的边。。所以还要设 $f_{i,j,S}$ 表示考虑到第 $i$ 个点，用了 $j$ 个集合，选择了 $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 = 15 + 1; int n,m,ha; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } // a < b : a -> b int small[(1<<MAXN)+3],big[(1<<MAXN)+3]; int f[MAXN][(1<<MAXN)+3]; // 选出了 S 内 i 组,组内相同的方案数 // 每次从小到大划分组 int tmp[MAXN]; inline int C(int n,int m){ if(n < m) return 0; FOR(i,1,m) tmp[i] = n-i+1; FOR(i,2,m){ int x = i; FOR(j,1,m){ int g = std::__gcd(tmp[j],x); x /= g;tmp[j] /= g; } } int ans = 1; FOR(i,1,m) ans = 1ll*ans*tmp[i]%ha; return ans; } int main(){ scanf("%d%d%d",&m,&n,&ha);//ha = 998244353; FOR(i,0,m-1){ int k;scanf("%d",&k); while(k--){ int x;scanf("%d",&x);--x; small[1<<i] |= (1<<x); big[1<<x] |= (1<<i); } scanf("%d",&k); while(k--){ int x;scanf("%d",&x);--x; small[1<<x] |= (1<<i); big[1<<i] |= (1<<x); } } FOR(S,0,(1<<m)-1){ FOR(i,0,m-1){ if((S>>i)&1){ small[S] |= small[S^(1<<i)]; big[S] |= big[S^(1<<i)]; } } } f[0][0] = 1; FOR(i,0,m-1){ FOR(S,0,(1<<m)-1){ if(!f[i][S]) continue; int s = ((1<<m)-1)^S; for(int T = s;T;T = (T-1)&s){ if(((big[T]&S) == 0)){ add(f[i+1][S^T],f[i][S]); } } } } int ans = 0; FOR(i,1,m) (ans += 1ll*C(n,i)*f[i][(1<<m)-1]%ha) %= ha; printf("%d\n",ans); return 0; }
A手玩一下样例，我们从大到小确定每个数：将确定的数挪到序列的最前面，设确定了 $x$ 个数，那么 $x \times x$ 的方格的数都没用了，并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值，所以我们只需要每次取最大值，将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。B可以猜测一下选择方案一定是前面可能有某些增加值的地方，后面值就一直不变了。所以我们先一直跑 dp，跑到快要 T 的时候就相当于要从剩下的块中选出一些数字。由于我们可以将这个块添加到任意位置，所以选最大出现次数的数字即可。可以证明其实只需要跑 $n$ 块即可。。因为你最坏情况是每一块增加一次。这一块不增加后面完全没有必要增加。C一个经典结论是设长度为 $s$，设 $g = \gcd(s,n)$，那么新的序列的第 $i$ 位会对应原序列的 $i,i+g,i+2g,\ldots i+kg$ 位。所以我们复制一遍序列，枚举 $g|n$，将下标按照 $\bmod g$ 分类，一个点合法当前仅当它是和它一组中的最大值，一个方案合法当且仅当区间内所有点合法，倒着扫一遍维护一个指针，差分维护前缀加，求出所有长度的区间的方案数，判断 $\gcd$ 即可解决。注意这里需要预处理一下 $\gcd(i,n)$，要不然会 T。。时间还是很紧的。D设 $v_p(x)$ 表示 $x$ 的唯一分解中 $p$ 上面的指数。首先我们有 $v_p(n!) = \sum_{i \geq 1} \lfloor \frac{n}{p^i} \rfloor$，并且还有 $v_p(ab) = v_p(a)+v_p(b)$，如果考虑将 $n$ 分解成 $p$ 进制下的数，那么 $v_p(n!)$ 的每一位贡献都是将比这一位低的位都去掉的数的和。那么我们知道 $v_p(\binom n m) = v_p(n!)-v_p(m!)-v_p((n-m)!)$，我们考虑 $m+(n-m) = n$ 这个加法运算，如果在第 $i$ 位它进位了，那么在前 $i$ 位贡献不变，在第 $i+1$ 位答案会多 $1$。所以 $v_p(\binom n m)$ 就是 $n-m$ 和 $m$ 做 $p$ 进制下加法的进位次数。这个好像叫做库默尔定理？然后我们可以考虑设计一个数位dp：我们在第 $i$ 位需要知道它后面那一位是否进位才可以确定限制等因素，设 $f_{i,j,0/1,0/1}$ 从高到低考虑前 $i$ 位，进了 $j$ 次位，当前的和是否卡上界，下一位是否进位，转移细节可以看代码（我注释写的很详细了）。#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 = 3500+5; const int ha = 1e9 + 7; const int inv2 = (ha+1)>>1; int p,_,n; char str[MAXN]; int b[MAXN],a[MAXN]; int f[2][MAXN][2][2],now; // 考虑前i位 当前进位了j次 现在是否卡上界 下一位是否进位 inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } inline int calc(int n){ // sum of [x <= b,y <= n,x+y <= n] if(n < 0) return 0; if(n == 0) return 1; return (1ll*(n+1)*(n+1)%ha+ha-1ll*n*(n+1)%ha*inv2%ha)%ha; } inline int calc2(int n){ // sum of [x <= p-1,y <= p-1,x+y <= n] // p <= n+1-i => i <= n+1-p int res = 0; if(n+1-p >= 0) add(res,1ll*(n+1-p+1)%ha*p%ha); // p > n+1-i => i >= n+2-p if(n+2-p <= p-1){ // p-1 +p-2 + .... int len = (p-1)-(n+2-p)+1; add(res,1ll*(p-1)*p%ha*inv2%ha); len = (p-1)-len; if(len > 0) add(res,ha-1ll*(len+1)*len%ha*inv2%ha); } return res; } int main(){ scanf("%d%d",&p,&_);// 进制转换 scanf("%s",str+1);int len = strlen(str+1); FOR(i,1,len) a[i] = str[i]-'0'; std::reverse(a+1,a+len+1); while(len){ int t = 0; ROF(i,len,1) t = (10ll*t+a[i]) % p; b[++n] = t; a[1] -= t; FOR(i,1,len){ if(a[i] < 0){ int tt = (-a[i])/10; if(a[i]+10*tt < 0) ++tt; a[i] += 10*tt; a[i+1] -= tt; } } while(len && !a[len]) --len; LL r = 0; // up to O(p^2) ROF(i,len,1){ r = 10*r+a[i]; a[i] = r/p; r %= p; } while(len && !a[len]) --len; } std::reverse(b+1,b+n+1); f[now=0][0][1][0] = 1; // int tt = 0;FOR(x,0,p-1) FOR(y,0,p-1) tt += (x+y <= 3); // DEBUG(tt);DEBUG(calc2(3)); // DEBUG(calc2(3)-calc2(2)); // exit(0); FOR(i,1,n){ // 打破限制 <=> (x+y)%p < b[i] // 有进位 <=> x+y>=p // 无进位 <=> x+y <= p-1 // 卡上界 <=> (x+y)%p = b[i] // +1 <=> 这一位的值 +1= // 这一位有限制 上一位必然有限制 // (x+1)^2-x*(x+1)/2 CLR(f[now^1],0); FOR(j,0,i){// 设两个数分别为x,y int t = 0; int c1 = calc(p-1); int c2 = calc(p-2); int c3 = calc(b[i]-1); int c4 = (calc2(p+b[i]-1)+ha-calc2(p-1))%ha; add(f[now^1][j][0][0],1ll*f[now][j][0][0]*(c1/*不进位*/)%ha); add(f[now^1][j][0][0],1ll*f[now][j][0][1]*(c2/*有进位*/)%ha); add(f[now^1][j][0][0],1ll*f[now][j][1][0]*(c3/*打破限制 不进位*/)%ha); add(f[now^1][j][0][0],1ll*f[now][j][1][1]*(c4/*打破限制 有进位*/)%ha); c1 = calc(p-2); c2 = calc(p-2);add(c2,p); c3 = calc(b[i]-2); c4 = (calc2(std::min(2*p-2,b[i]+p-2))+ha-calc2(p-2))%ha; add(f[now^1][j+1][0][1],1ll*f[now][j][0][0]*(c1/*不进位 +1*/)%ha); add(f[now^1][j+1][0][1],1ll*f[now][j][0][1]*(c2/*有进位 +1*/)%ha); add(f[now^1][j+1][0][1],1ll*f[now][j][1][0]*(c3/*打破限制 不进位 +1*/)%ha); add(f[now^1][j+1][0][1],1ll*f[now][j][1][1]*(c4/*打破限制 有进位 +1*/)%ha); c3 = b[i]+1; c4 = std::min(b[i]+p,p-1)-std::max(1+b[i],0)+1; c4 = std::max(c4,0); // add(f[now^1][j][1][0],f[now][j][0][0]*(/*不存在*/)); // add(f[now^1][j][1][0],f[now][j][0][1]*(/*不存在*/)); add(f[now^1][j][1][0],1ll*f[now][j][1][0]*(c3/*卡上界 不进位*/)%ha); add(f[now^1][j][1][0],1ll*f[now][j][1][1]*(c4/*卡上界 有进位*/)%ha); c3 = b[i]-1+1; c4 = std::min(b[i]+p-1,p-1)-std::max(1-p+b[i]+p-1,0)+1; // add(f[now^1][j+1][1][1],f[now][j][0][0]*(/*不存在*/)); // add(f[now^1][j+1][1][1],f[now][j][0][1]*(/*不存在*/)); add(f[now^1][j+1][1][1],1ll*f[now][j][1][0]*(c3/*卡上界 不进位 +1*/)%ha); add(f[now^1][j+1][1][1],1ll*f[now][j][1][1]*(c4/*卡上界 有进位 +1*/)%ha); } now ^= 1; } int ans = 0; FOR(i,_,n) add(ans,f[now][i][0][0]),add(ans,f[now][i][1][0]); printf("%d\n",ans); return 0; }E首先表达式问题肯定不能做，要建表达式树。建数每次扫出一个完整的括号就在这个地方划分就好了（详情请看代码）。发现只有 $4$ 个变量也就是 $16$ 种取值，我们相当于限制了在多个变量取值情况的总取值，所以我们考虑将所有可能取值的总取值都压缩起来：设 $f_{i,S}$ 表示 $i$ 子树内，变量取值为 $1$ 的集合 $T \in S$ 的时候总取值都为 $1$，其余都为 $0$ 的方案数。换言之 $S$ 是字母取值集合的集合（所以大小 $2^{16}$）。在底层的时候如果是确定的点就枚举所有的 $v \in T$，将这些 $T$ 组成的集合 $S$ 的 $f_{v,S} = 1$。如果不确定的话就把所有可能枚举一遍。这里要预处理所有类型的点而不是每次暴力要不然时间可能不太行。然后合并的时候相当于是一个集合并卷积或者集合交卷积，FWT即可。这种将所有可行的取值的状态压起来的状压还是要多想。。好好复习一下。#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 = 500+5; const int MAXM = 16; const int ha = 1e9 + 7; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } int ch[MAXN][2],tot; char a[MAXN],str[MAXN]; int rt; inline int work(int l,int r){ if(l > r) return 0; if(l == r){ a[++tot] = str[l]; return tot; } int sm = 0,ps = 0; FOR(i,l,r){ if(str[i] == '(') ++sm; if(str[i] == ')') --sm; if(sm == 0){ ps = i;break; } } if(ps == r) return work(l+1,r-1); int x = ++tot; a[x] = str[ps+1]; ch[x][0] = work(l+1,ps-1); ch[x][1] = work(ps+3,r-1); return x; } int f[MAXN][(1<<16)+3]; int g[9][(1<<16)+3]; // 子树v内, 四个字母每种可能的取值 T 对应的表达式取值集合是S,方案数 inline int ctoi(char c){ if(c >= 'A' && c <= 'D') return c-'A'; if(c >= 'a' && c <= 'd') return c-'a'; return -1; } int N = (1<<16); inline void OR(int f[]){for(int mid = 1;mid < N;mid <<= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+mid+j],f[i+j]);} inline void iOR(int f[]){for(int mid = N>>1;mid;mid >>= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+mid+j],ha-f[i+j]);} inline void AND(int f[]){for(int mid = 1;mid < N;mid <<= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+j],f[i+mid+j]);} inline void iAND(int f[]){for(int mid = N>>1;mid;mid >>= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+j],ha-f[i+mid+j]);} inline void COR(int A[],int B[],int C[]){OR(A);OR(B);FOR(i,0,N-1) C[i] = 1ll*A[i]*B[i]%ha;iOR(C);iOR(A);iOR(B);} inline void CAND(int A[],int B[],int C[]){AND(A);AND(B);FOR(i,0,N-1) C[i] = 1ll*A[i]*B[i]%ha;iAND(C);iAND(A);iAND(B);} int tmp[(1<<16)+5]; inline void dfs(int v){ if(!ch[v][0] && !ch[v][1]){ int id = ctoi(a[v])+(4*(a[v] >= 'a' && a[v] <= 'd')); if(id == -1) id = 8; FOR(S,0,(1<<16)-1) f[v][S] = g[id][S]; return; } dfs(ch[v][0]);dfs(ch[v][1]); if(a[v] == '&') return CAND(f[ch[v][0]],f[ch[v][1]],f[v]); if(a[v] == '|') return COR(f[ch[v][0]],f[ch[v][1]],f[v]); CAND(f[ch[v][0]],f[ch[v][1]],tmp); COR(f[ch[v][0]],f[ch[v][1]],f[v]); FOR(S,0,N-1) add(f[v][S],tmp[S]); } int main(){ FOR(i,0,3){ int t = 0; FOR(S,0,(1<<4)-1) t |= (((S>>i)&1)<<S); ++g[i][t];++g[i+4][t^((1<<16)-1)]; ++g[8][t];++g[8][t^((1<<16)-1)]; } scanf("%s",str+1);int len = strlen(str+1); rt = work(1,len); dfs(rt); int n;scanf("%d",&n); int t0=0,t1=0; FOR(i,1,n){ int a,b,c,d,e;scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); int t = a|(b<<1)|(c<<2)|(d<<3); if(e) t1 |= (1<<t); else t0 |= (1<<t); } int ans = 0; FOR(S,0,(1<<16)-1) if(((S&t1) == t1) && ((S&t0) == 0)) add(ans,f[rt][S]); printf("%d\n",ans); return 0; }
A贪心想法先把 $a$ 和 $b$ 拼成若干个 $ab$，然后如果有剩余的可以在对应的开头/结尾放，所以答案是 $c+\min(a,b)+[a \neq b]$。B枚举我们强制让这个人 $A \to B$ 选择那一班航班起飞（这样就相应 ban 掉了一些航班），然后双指针维护处对应的 $B \to C$ 最近能从哪里开始起飞，就是查一个第 $x$ 大的问题了。因为排好序了可以 $O(1)$ 直接求出。C我们只需要实现 $5$ 步内交换两个数的算法就好了：我们考虑交换 $(x,y)$ 的最一般的情况：$1 < x \leq \frac{n}{2} < y < n$，这样我们需要交换 $(x,n),(y,1),(1,n),(x,n),(y,1)$。需要额外判断一下 $x < y < \frac{n}{2}$，$\frac{n}{2} > x > y$，$x = 1,y = n$ 的各种情况，都能在五步内完成。然后直接每次将对应的值交换到正确的位置上就好了。D要看到能任意交换顺序这一点。不然就只会垃圾做法了。我们将 $a_i < b_i$ 和 $a_i > b_i$ 分成两组，发现两组内的数不能放在一起，于是可以分开处理。以解决 $a_i < b_i$ 为例：一个 sb 的想法是树状数组优化 dp，但是真的是这样么？我们考虑相邻的两个元素 $a_1 < b_1 > a_2 < b_2$，那么如果 $b$ 越小 $a$ 就越小，所以我们肯定按照 $b$ 从大到小排序，发现 $b_1 > b_2,a_2 < b_2 \Rightarrow b_1 > a_2$，这样就全满足了。另一组讨论是类似的。这个问题还是要好好读题，然后在草稿纸上画一画这些组，发现一些性质就好了。E又是可以随便排列顺序。。读题一定要仔细了。。那么我们肯定贪心从大到小排序然后考虑调整：如果一个位置想要减小，一定是找一个后面想要变大的匹配。所以我们记一下当前想要变小的位置和要变小多少，每次如果 $s_i > t_i$ 就把 $i$ 扔到集合内，否则就不断从集合头匹配即可。如果找不到前面的一个数匹配或者是最后没有匹配完就无解。感觉操作次数 $\leq 2n$ 啊不知道范围是个什么迷惑操作。。F考虑先使用归纳法证明一定有解：首先如果 bit 只有 $1$ 位一定有解：直接翻转即可。那么假设 bit 有 $k$ 位有解，接下来我们想证明 $k+1$ 位有解。发现当前翻转 $k+1$ 位上的若干位数不会影响最高位 $\leq k$ 的数，所以判断一下是否需要翻转即可。需要注意虽然我们每次决定是否翻转只是看最高位是 $k+1$ 的数，但是翻转的时候是要全部都翻转的。G好神仙啊。。。首先发现如果得到一个 $k$ 的好的集合，那么一定能得到 $\leq k$ 的好的集合。但是得到了大小为 $k$ 的不好的集合不代表你能得到 $\leq k$ 的好的集合。首先我们考虑 $O(n^2)$ 的暴力怎么做（小蒟蒻这个都不会）：如果 $k$ 是偶数：我们任意选出 $k$ 个数，每次先判断一下是不是组成一个团，如果组成直接输出，否则一定存在一对点之间没有边，删除这两个点，并且找这个点的两个相邻的点放入这个集合。如果操作 $\frac{k}{2}$ 次仍然无解，被删除的点的集合一定满足是不好的。如果 $k$ 是奇数：我们一开始找到三个点 $u,v,w$ 满足 $(u,v),(v,w)$ 边不存在，删去这三个点做子问题，可以得到一个偶数大小的不好集合，最后考虑是否要加入这三个点即可。选择三个点而不是一个点的原因是三个点可以自由决定是否加两个/三个，但是一个点加入之后你不知道是不是会破坏不好的性质。如果找不到这三个点，考虑这个图的补图，补图一定是森林，好的集合对应一个独立集，黑白染色可知一定存在 $\geq \frac{n}{2}$ 的独立集，只需要在一开始判掉有好集合的情况就好了。道理我都懂，但是正解怎么做呢？我们可以用一个复杂度 $O(2^8 n \log n)$ 的复杂度解决。首先可以将所有数的唯一分解后的形式的 $>0$ 的指数都改成 $1$，不难发现这样不影响图的形态。考虑整张图的形态显然是不行的，那么遇到这种问题一定先考虑某些特殊量是否能被算出：首先我们先考虑如何快速算一个点的度数，可以用 $f_i$ 记录包含因子 $i$ 的数的个数然后 $2^8$ 运用容斥原理算出。类似地我们选出三个点 $u,v,w$，满足 $(u,v),(v,w)$ 边不存在，并删去这三个点。我们对剩下的点，设和其他所有点都有连边的数量是 $b$，如果 $b \geq k$ 直接输出答案即可，否则剩下的 $n-3-b$ 个元素组成的集合是不好的。因为 $u,v,w$ 之间无边，所以可以全部加入到任意不好的集合内而不破坏性质。考虑有 $b < k \leq \frac{n}{2}$ ，所以 $n-3-b+3 = n-b > n-\frac{n}{2} = \frac{n}{2} \geq k$，所以一定存在一个大小 $\geq k$ 的不好的集合。现在我们就要考虑如何删除一些数而不破坏性质：我们设 $f(r)$ 表示 $[1\ldots r]$ 数能选出最大的不好的集合，通过二分找到第一个位置 $r$ 满足 $f(r) \geq k,f(r-1) < k$，观察一下可以发现这说明了有 $f(r)-f(r-1)-1$ 个点与前 $r-1$ 个点连边，但是与 $r$ 点不连边，并且 $r$ 点也是不好点。所以我们可以删除这些点而不影响性质（因为其他点都是连到这个点上的，不依赖于它而保持不好的性质），我们发现至多删除 $f(r)-f(r-1)-2$ 个点（因为如果全删了可能 $r$ 点就是好点了），所以经过删除后我们能得到大小为 $k$ 或者 $k+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 = 1e5 + 5; const int MAXM = 1e7 + 5; bool p[MAXM]; int prime[MAXM],cnt; inline void prework(){ FOR(i,2,MAXM-1){ if(!p[i]) prime[++cnt] = i; for(int j = 1;j <= cnt && 1ll*i*prime[j] < MAXM;++j){ p[i*prime[j]] = 1; if(!(i%prime[j])) break; } } } int n,k; int a[MAXN]; std::vector<int> G[MAXN],v[MAXM]; inline void reduce(int i){ int x = a[i],q = std::sqrt(1.0*x); FOR(j,1,cnt){ int p = prime[j]; if(p > x || p > q) break; if(!(x%p)){ int c = 0;v[j].pb(i);G[i].pb(p); while(!(x%p)) ++c,x /= p; --c;while(c--) a[i] /= p; } } if(x != 1){ G[i].pb(x); int p = std::lower_bound(prime+1,prime+cnt+1,x)-prime; v[p].pb(i); } } int f[MAXM]; // 求有多少个和它不互质 枚举gcd容斥即可 int b[MAXN]; inline int deg(int i){ int sz = G[i].size(),res = 0; FOR(S,1,(1<<sz)-1){ int t = 1; FOR(j,0,sz-1){ if((S>>j)&1) t *= G[i][j]; } int gx = f[t]; if((__builtin_popcount(S)-1)&1) gx = -gx; res += gx; } return res-1; } inline void add(int i,int d){ int sz = G[i].size(); FOR(S,1,(1<<sz)-1){ int t = 1; FOR(j,0,sz-1){ if((S>>j)&1) t *= G[i][j]; } f[t] += d; } } int m; inline int chk(int x){ FOR(i,x+1,m) add(b[i],-1); int c = 0; FOR(i,1,x) c += (deg(b[i]) == x-1); FOR(i,x+1,m) add(b[i],1); return x-c+3; } bool vis[MAXN]; std::mt19937 g(19260); int tt[MAXN]; int main(){ prework(); scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d",a+i),tt[i] = a[i],reduce(i); FOR(i,1,cnt){ if(v[i].size() >= k){ FOR(j,0,k-1) printf("%d ",v[i][j]); puts(""); return 0; } } FOR(i,1,n) add(i,1); int u=-1,v=-1,w=-1; FOR(i,1,n){ if(n-1-deg(i) >= 2){ v = i; FOR(j,1,n){ if(j == i) continue; if(std::__gcd(a[i],a[j]) > 1) continue; if(u == -1) u = j; else w = j; } break; } } add(u,-1);add(v,-1);add(w,-1); if(k == 3){ printf("%d %d %d\n",u,v,w); return 0; } FOR(i,1,n){ if(i == u || i == v || i == w) continue; b[++m] = i; } int c = 0; FOR(i,1,m) if(deg(b[i]) == m-1) ++c; if(c >= k){ c = 0; FOR(i,1,m){ if(deg(b[i]) == m-1) ++c,printf("%d ",b[i]); if(c == k) break; } puts(""); return 0; } int l = 1,r = m,ans = -1; while(l <= r){ int mid = (l + r) >> 1; if(chk(mid) >= k) ans = mid,r = mid-1; else l = mid+1; } int _ = chk(ans),t = _-chk(ans-1)-2,d = _-k; FOR(i,ans+1,m) add(b[i],-1); FOR(i,1,ans) vis[i] = (deg(b[i]) != ans-1); FOR(i,1,ans-1){ if(!d) break; if(t <= 0) break; if(!vis[i]) continue; if(std::__gcd(a[b[i]],a[b[ans]]) != 1) continue; if(deg(b[i]) != ans-2) continue; --d;--t;vis[i] = 0; } FOR(i,1,ans) if(vis[i]) printf("%d ",b[i]); if(!d) printf("%d ",u); printf("%d %d\n",v,w); return 0; }H还在咕咕咕
A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小排序即可。因为无论如何放最后一个未锁定的位置的前缀和不会变，那么肯定先把所有最大的都用上去尽量 cover 掉小的贡献。Cdp。设 $f_{i,0/1}$ 表示打了前 $i$ 关，轮到玩家还是玩家的朋友打的最小代价，直接枚举转移即可。D假设两个位置选择的分别是 $x_1,x_2(x_1 < x_2)$，把坐标排好序后肯定存在一个分解点 $mid$，满足 $i \leq mid$ 都走到 $x_1$，并且 $i > mid$ 都走到 $x_2$。设第 $i$ 个坐标位置 $p_i$，发现这样的代价为 $p_n-p_1-(p_{mid+1}-p_{mid})$，所以实际上是要你支持插入，删除，维护相邻差的最大值，用两个 multiset 就可以了。E根据期望的线性性，我们只需要计算每一个 boss 对玩家的期望伤害即可。boss 可以分为两类：一类是会削玩家护盾耐久的，一类是螳臂当车的。对于会削玩家护盾耐久的，设这样的 boss 有 $m$ 个，能打到玩家的概率是 $\frac{m-a_i}{m}$（因为它在这 $m$ 个数的相对排名只有 $m$ 种情况，后面 $m-a_i$ 种是合法的）对于螳臂当车的 boss，设这样的 boss 有 $k$ 个，能打到玩家的概率是 $\frac{m+1-a_i}{m+1}$。（因为它只能选择 $m+1$ 个空插进去，后面 $m+1-a_i$ 个空是合法的）分开乘起来就行。多组询问只需要离线排序，变成了维护每次将一个削玩家耐久的变成螳臂当车的boss的操作，记录一下权值和就行了。F发现一个结论：对于任何一对 $x_1y_1 = x_2y_2(x_1 < x_2)$，都存在一对正整数 $a < b$，满足 $x_2 = \frac{x_1}{a}b,y_2 = \frac{y_1}{b}a$。[collapse status="false" title="证明"]设 $g=\gcd(x_1,x_2)$，我们构造 $a=\frac{x_1}{g},b = \frac{x_2}{g}$，不难发现 $\frac{x_1}{a}b = x_2$，接下来只需要证明 $b|y_1$即可。注意到 $b=\frac{x_2}{g} | \frac{x_2y_2}{g} = \frac{x_1y_1}{g}$，又因为有 $(b,\frac{x_1}{g}) = 1$，所以得到 $b|y_1$。[/collapse]因为 $a|x_1,b|y_1$，所以有效的 $(a,x_1)$ 只有 $O(n \log n)$ 对。现在我们去固定 $x_1$，考虑 $y_1$ 的种种限制：首先要保证 $y_1 \leq m$，其次还要保证 $\lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor$。我们考虑枚举一对 $(a,x_1)$，现在相当于要求快速询问是否存在一对 $(b,y_1)$ 满足如下条件：$$ \begin{aligned} y_1 \leq m\\ \lceil \frac{L}{x_1}\rceil \leq y_1 \leq \lfloor \frac{R}{x_1} \rfloor\\ \frac{x_1}{a}b \leq n\\ a < b \end{aligned} $$显然我们会贪心选择能选择的 $b$ 中最小的去判断第三个限制是否成立。第一个和第二个限制可以通过从小到大枚举 $x$ 双指针解决，第四个限制可以维护当前所有可选值的 set 解决，复杂度 $O(n \log^2 n)$。G确定性做法我们考虑枚举右端点，维护每个左端点是否合法。我们的目标是让对于每一种颜色，如果左端点区间是合法的，贡献就是 $0$，否则贡献是 $1$。那么一个左端点合法当且仅当这个位置的值是 $0$。我们每次加入一个点 $i$，设它前面第一个，第二个，第三个，第四个和它相等的是 $p_1,p_2,p_3,p_4$，我们只需要让 $(p_1,i]+1$，$(p_3,p_2]-1$，$(p_4,p_3]+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 = 5e5 + 5; int a[MAXN],n; #define lc ((x)<<1) #define rc ((x)<<1|1) int mn[MAXN<<2],cnt[MAXN<<2],tag[MAXN<<2]; inline void pushup(int x){ mn[x] = std::min(mn[lc],mn[rc]);cnt[x] = 0; if(mn[x] == mn[lc]) cnt[x] += cnt[lc]; if(mn[x] == mn[rc]) cnt[x] += cnt[rc]; } inline void cover(int x,int d){ mn[x] += d;tag[x] += d; } inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(L > R) return; if(l == L && r == R){ cover(x,d);return; } int mid = (l + r) >> 1;pushdown(x); 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); pushup(x); } inline void build(int x,int l,int r){ if(l == r){ cnt[x] = 1;mn[x] = 1e9;return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); pushup(x); } int lst[MAXN],pre[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); FOR(i,1,n){ pre[i] = lst[a[i]]; lst[a[i]] = i; } build(1,1,n);LL ans= 0; FOR(i,1,n){ int p1 = pre[i],p2 = pre[p1],p3 = pre[p2],p4 = pre[p3]; modify(1,1,n,i,i,-1e9); modify(1,1,n,p1+1,i,1); if(p2) modify(1,1,n,p3+1,p2,-1); if(p3) modify(1,1,n,p4+1,p3,1); if(mn[1] == 0) ans += cnt[1]; } printf("%lld\n",ans); return 0; }基于随机的做法出现三次不难联想到三进制不进位加法。我们对于每个数字随机一个 $60$ 维模 $3$ 意义下的向量，前缀和后两个位置前缀和相同就表示这一段区间所有出现次数 $\bmod 3=0$，但是我们想要的是 $=3$，我们只需要用双指针维护出满足所有颜色出现次数 $\leq 3$ 的区间即可。出题人说：[scode type="blue"]Assume you use $K$ trits. I guess the probability of the collision is the same as two vectors (out of $n$) colliding in a $K$ - dimensional space with their coordinates being from $0$ to $2$. That will be about $\frac{1}{2}$ when $n≈3^K$ (according to birthday paradox) — and way less if we increase $K$.[/scode]
A因为 $\gcd$ 是指数取 min，$\text{lcm}$ 是指数取 max，所以我们对于每一个质数分开考虑。设第 $i$ 个数唯一分解后在这个质数上的指数是 $e_i$，设次小值是 $cmx$，答案贡献 $p^{cmx}$。具体实现的时候质因数分解一下即可。B首先序列里一定要有 $k$ 这个值。如果 $k$ 两边有一个 $\geq k$ 的数，就可以把这两个数都变成 $k$，然后每次选择这两个数和周围的一个数就可以合并起来了。所以等价于我们能选出一个中位数 $\geq k$ 的区间。[collapse status="false" title="证明"]我们找到一个中位数 $\geq k$ 的区间，如果这个区间没有包含所有的 $k$，那么可以任意调节长度然后对整体操作；如果包含了所有的 $k$，肯定能找到一个位置把它分成两段，某一段和为 $0$。然后直接操作即可。如果没有这样的区间，$\geq k$ 的数每次操作后不会增加，最终不会合法。[/collapse]C这个和那个真正的的生命游戏不一样！！迷惑了我半天我们发现如果一个数周围至少有一个和它相同的数，那么这两个数就会一起持续变颜色。所以我们只需要求出来所有点从什么时候开始周期变颜色就好了。可以把一开始就变色的点都扔进 queue 里，每个点向周围连边，跑一个边权为 1 的 bfs。D以下题目设 $m=\sum_{i=1}^n a_i$期望题肯定先拆开看看啊。但是我想不到怎么设。设 $E_i$ 表示到 $i$ 个点结束的答案的和（所有情况的概率乘时间的和），$E'_i$ 表示强制到 $i$ 点结束的期望时间，$P_i$ 表示在 $i$ 点结束的概率，$C$ 表示饼干从 $i$ 全部转移到 $j$ 的期望时间（显然都相等）。观察可以发现 $\sum_{i=1}^n P_i = 1,ans = \sum_{i=1}^n E_i$。首先可以得到$$ E_x = E'_x-\sum_{i=1}^n [x \neq i] (E_i+P_iC) $$就是枚举第一个到达的点是哪里，然后走过来（$E_i+P_iC$ 的理解只需要把 $E_i$ 拆成所有情况的概率乘时间的和就行了）。移项可得$$ \sum_{i=1}^n E_i = E'_x-C\sum_{i=1}^n [x \neq i]P_i $$两边对 $x$ 从 $1$ 到 $n$ 求和，可以得$$ ans = \frac{\sum_{i=1}^n E'_x-(n-1)C}{n} $$所以目标就是求 $E'_x$ 和 $C$。发现这两个东西之和目标的人有多少个饼干有关，设 $f_x$ 表示目标人有 $x$ 块饼干，到有全部饼干的期望时间。考虑这一步的饼干选出情况可以得到：$$ f_i = \begin{cases} 1+\frac{m-i}{m}(\frac{1}{n-1}f_{i+1}+\frac{n-2}{n-1}f_i)+\frac{i}{m}f_{i-1} & 0 < i < m\\ 1+\frac{n-2}{n-1}f_1+\frac{1}{n-1}f_0& i=0\\ 0&i=m \end{cases} $$这样直接高斯消元理论上就行了，但是实际上会遇到系数是模数倍数的情况然后就会被叉死。所以我们考虑能否改成一个线性递推：发现这个式子 $f$ 的系数和为 $1$，对于这样的式子我们考虑把 $f_i$ 表示成前缀和（后缀和）能消掉一个方向的所有东西就好了。为了方便我们设 $g_i = f_{i}-f_{i+1},f_{m+1}=0$，容易得到 $f_{i} = \sum_{j=i}^m g_i$。所以我们把 $0 < i < m$ 的式子拿出来看看：$$ \begin{aligned} \sum_{j=i}^m g_j = 1+\frac{n-i}{m}(\frac{1}{n-1}\sum_{j=i+1}^mg_j+\frac{n-2}{n-1}\sum_{j=i}^m g_j)+\frac{i}{m}\sum_{j=i-1}^m g_j\\ \end{aligned} $$注意到 $\frac{m-i}{m}(\frac{1}{n-1}+\frac{n-2}{n-1})+\frac{i}{m} = 1$，式子可以简化为$$ \begin{aligned} g_i = 1+\frac{n-i}{m}\times \frac{n-2}{n-1}g_i+\frac{i}{m}(g_i+g_{i+1})\\ \frac{m-i}{m(n-1)}g_i = 1+\frac{i}{m}g_{i-1}\\ g_i = \frac{m(n-1)}{m-i}+\frac{i(n-1)}{m-i}g_{i-1} \end{aligned} $$然后只需要求出 $g_0$ 就可以递推了。我们发现：$$ \begin{aligned} g_0 = f_0-f_{1}\\ f_0 = 1+\frac{n-2}{n-1}f_0+\frac{1}{n-1}f_1\\ \end{aligned} $$联立可以求出 $g_0 = n-1$。递推即可。不会出现高斯消元系数是模数倍数最后除 $0$ 直接 RE 那么鬼畜的情况了。E这种看帽子的问题很有意思，我不会做，于是写一下题解思路吧。首先我们先把标号倒过来，假设 $n$ 在最前面。定义 $t_i$ 表示第 $i$ 个人的离开时间，$c_i$ 表示颜色。先考虑直到颜色如何求时间。我们设从前往后第一个黑色是 $x$，讨论两种情况：$x=1$，$1$ 看到前面都是白色+知道有黑色就在第一轮跑路了，剩下的人就在第二轮跑路了，$t_1=1,t_i=2(i\geq 2)$$x \geq 2$，$1$ 不能确定所以不跑路，所以大家都知道了 $\geq 2$ 的人有黑色，就相当于变成了 $2\ldots n$ 的子问题。直到 $x$ 轮，$x$ 就可以跑路了，剩下的 $x+1\ldots n$ 在 $x+1$ 轮跑路并且变成了 $1\ldots x-1$ 的子问题，$t_x=1$,$t_i=2(i > x)$。于是我们可以方便求出 $t$ 的值，对于每一个位置 $i$：$c_i=1$，则 $t_i = \sum_{j > i,c_j=1}j$，此时记 $b_i=i$$c_i=0$，设 $k$ 是它后面第一个黑色，则 $t_i = t_k+1$，记 $b_i=k$。发现二情况可能没人，所以我们在 $0$ 位置加一个 $t_0=\sum_{c_j=1}j$ 的不参加游戏的人即可。这样就都是良定义的。所以我们求出来 $b_i$ 后就可以用 $t_i = t_{b_i}+(1-c_i)$ 求时间了。现在考虑如何做原问题：首先观察一下，对于 $i \geq j$，如果 $c_i = c_j = 1$，一定有 $t_i \leq t_j$。又对于 $i > j$，有 $b_i \geq b_j$，所以$$ \forall i > j,t_i-t_j = t_{b_i}+(1-c_i)-t_{b_j}-(1-c_j) = t_{b_i}-t_{b_j}+(c_j-c_i) \leq c_j-c_i \leq 1 $$分类讨论可以得到：$$ \left\{\begin{array}{l}t_{i}-t_{j}=1, \text { if } c_{j}=1 \text { and } \forall i \geq k>j, c_{k}=0 \\ t_{i}-t_{j}=0, \text { if } \exists i>k>j, c_{k}=1, c_{1}=c_{2}=\cdots=c_{k-1}=c_{k+1}=\cdots=c_{n}=0 \text { or } \forall i \geq k \geq j, c_{k}=0 \\ t_{i}-t_{j}<0, \text { otherwise }\end{array}\right. $$于是如果我们把区间分成满足 $i>j,t_i-t_j \geq 0$ 的合并，一定形成了若干不交区间，如果 $l_i \neq 1$ 就会满足：$c_{l+1}=c_{l+1}=\ldots=c_r=0$$b_l = b_{l+1}=\ldots=b_r$，记其为 $B[l,r]$显然 $B$ 越大越好（后面可分配空间越多）于是我们可以对这个东西 dp：设 $f_{i,0/1}$ 表示处理好了 $i\ldots m$，当前这一段的 $c_{l_i} = 0/1$ 的最大的 $B$。从 $f_{i+1,j}$ 转移到 $f_{i,j'}$ 只需要枚举所有可能的 $f_{i,j'}$，判断一下：$$ t_{f_{i,j'}} = \sum_{k \geq f_{i,j'},c_k=1}k = \sum_{k \geq f_{i+1,j},c_k=1}k + \sum_{f_{i+1,j} > k \geq f_{i,j'},c_k=1}k = t_{f_{i+1},j}+f_{i,j'}+\sum_{r_i < j < f_{i+1,j},c_j=1}k $$相当于判断从 $[L,R]$ 中选出若干数，和是否能 $=x$。可以二分选了多少数，能得到区间 $[L+(L+1)+\ldots+(L+num-1),(R-num+1)+(R-num+2)+\ldots+R]$，判断一下就好了。对于 $l_i=1$ 的时候不满足上述性质，但是 $[l_1,r_1]$ 至多有一个 $i$ 满足 $c_i=1$，可以枚举 $1$ 的位置转移。代码就先咕咕咕咕了。F1首先这个限制条件这么诡异，我们肯定是要转化一下的（然而我思考的时候直接对着做人就没了）首先打表发现长度为 $n$ 的好的序列是 $n!$ 个，让我们联想到和排列联系在一起。对于一个排列：我们将其划分成若干段极长连续下降的段，对于第 $i$ 段里的一个数 $x$，令 $a_x=i$。[collapse status="false" title="举个栗子"]假设排列是 $[3,5,4,6,2,1]$，那么应该划分成$[3|5,4|,6,2,1]$，对应的序列就是 $[3,3,1,2,2,3]$。[/collapse]用这种构造方法不难证明它们之间建立了双射（只需要倒着再构造一次证另一个方向的结论就好了）相当于每有一个 <，填的数字就会 $+1$。我们先引入一个欧拉数的概念：$\left<^n_k \right>$，表示长度为 $n$ 的所有排列中，恰有 $k$ 个 $<$ 的排列个数。显然可以 dp 每次枚举插入位置得到：$$ \left<^n_k\right> = (k+1)\left<^{n-1}_{k}\right>+(n-k)\left<^{n-1}_{k-1}\right> $$那么我们在算 $x$ 的出现次数时，我们枚举每一个位置 $p$ 的贡献：显然是 $\left<^p_{x-1}\right>\binom n p (n-p)!$。组合意义就是首先前面的要划分成 $x$ 段（也就是 $x-1$ 个$<$，它是第 $x$ 段），然后选出一段值域赋给它，后面的没有限制随便排，就算完了这一个位置作为答案的次数了。F2你觉得我会二元拉格朗日反演？
题目链接题目大意有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足$$c_k=\max_{\gcd(i,j)=k}|a_i-b_j|$$$n \leq 10^5$题解我们先考虑拆绝对值：最后全部取反再做一遍就好了，式子变成了$$c_k=\max_{\gcd(i,j)=k}a_i-b_j$$发现我们只需要研究 $k=1$ 的情况就好了 其余的情况可以通过拿出含有这个因子的数来转化成是 $1$ 的情况 复杂度需要乘个调和级数。我们把 $b$ 取反 题目变成了$$ c_1=\max_{\gcd(i,j)=1} a_i+b_j \\=\max_{i=1}^n (a_i+\max_{\gcd(i,j)=1}b_j) $$考虑我们枚举 $i$ 如何去计算 $\max_{\gcd(i,j)=1}b_j$：暴力枚举不太友好 我们看到 $gcd$ 就想到了$\mu$ ，但是这里是 max 不能 $mu$。于是我们考虑二分最大的$b$，设为 $b'$，你需要检验$$ \begin{align*} \max_{\gcd(i,j)=1}b_j \geq b' \\ sum_{j=1}^n [\gcd(i,j)=1][b_j \geq b'] > 0 \\ sum_{j=1}^n [b_j \geq b']\sum_{d|i,d|j}\mu(d) > 0 \\ sum_{d|i}\mu(d)\sum_{d|j}[b_j \geq b'] > 0 \end{align*} $$我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。时间复杂度 $O(nlog^3n)$ 欣慰的是这个题不卡常（最近被卡常题做晕了）#include<bits/stdc++.h> #define fi first #define se second #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],B[MAXN],C[MAXN]; int a[MAXN],b[MAXN],c[MAXN]; int q[MAXN],tr[MAXN]; int now,sm[MAXN]; std::vector<int> dec[MAXN]; bool p[MAXN]; int prime[MAXN],mu[MAXN],cnt; inline void prework(){ mu[1] = 1; FOR(i,2,MAXN-1){ if(!p[i]) prime[++cnt] = i,mu[i] = -1; for(int j = 1;j <= cnt && i*prime[j] < MAXN;++j){ p[i*prime[j]] = 1;mu[i*prime[j]] = -mu[i]; if(!(i%prime[j])) {mu[i*prime[j]] = 0;break;} } } FOR(i,1,MAXN-1) for(int j = i;j < MAXN;j += i) dec[j].pb(i); } inline void work(int l,int r,int L,int R){ if(l > r) return; if(L == R){ FOR(i,l,r) c[q[i]] = L; return; } int mid = (L+R)>>1; while(now > mid){ int x = tr[now--]; for(auto i:dec[x]) ++sm[i]; } while(now < mid){ int x = tr[++now]; for(auto i:dec[x]) --sm[i]; } std::vector<int> toL,toR; FOR(i,l,r){ int t = 0; for(auto d:dec[q[i]]) t += mu[d]*sm[d]; if(t > 0) toR.pb(q[i]); else toL.pb(q[i]); } int tp = l-1,sz = toL.size(); for(auto x:toL) q[++tp] = x; for(auto x:toR) q[++tp] = x; toL.clear();toR.clear(); work(l,l+sz-1,L,mid);work(l+sz,r,mid+1,R); } inline int solve(int n){ std::vector<int> S;now = n; FOR(i,1,n) S.pb(b[i]);std::iota(q+1,q+n+1,1); std::fill(sm+1,sm+n+1,0);std::sort(all(S)); FOR(i,1,n){ int x = std::upper_bound(all(S),b[i])-S.begin(); tr[x] = i; S[x-1]++; } work(1,n,1,n);int ans = -1e9; FOR(i,1,n) ans = std::max(ans,a[i]+S[c[i]-1]-1); return ans; } inline void Solve(){ FOR(i,1,n){ for(int j = 1;j*i <= n;++j){ a[j] = A[i*j]; b[j] = B[i*j]; } C[i] = std::max(C[i],solve(n/i)); // exit(0); } } int main(){ scanf("%d",&n);prework(); FOR(i,1,n) scanf("%d",A+i); FOR(i,1,n) scanf("%d",B+i),B[i] = -B[i]; Solve(); FOR(i,1,n) A[i] = -A[i],B[i] = -B[i]; Solve(); FOR(i,1,n) printf("%d ",C[i]); return 0; }