有 n 个互不相同的正整数，记作x1,x2,x3,…,xn 记 A={1,2,3,…,n} 求 ∑a⊂A,a≠∅F(a) mod 109+7 在这里， F(a)=maxi,j∈a|xi−xj| 1≤n≤3∗105，1≤xi≤109
不妨将 xi 按照升序排好 对于 F(a)=maxi,j∈a|xi−xj| 注意到这个函数其实只跟集合 a 中的最大值和最小值有关 那么就枚举所有可能的情况，乘上合法集合个数就行了 具体的，枚举xi和 xj 中的数字个数 k 强制xi和 xj 必须出现在集合中，这样合法集合个数有 2k 枚举 k 从1→n−1，端点的值的和可以用前缀和后缀和统计
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 3E5 + 3; const int mo = 1000000007; int n,Ans,A[maxn],pre[maxn],suf[maxn]; #define Mul(x,y) (1LL * (x) * (y) % mo) #define Add(x,y) ((x) + (y) < mo ? (x) + (y) : (x) + (y) - mo) #define Dec(x,y) ((x) - (y) >= 0 ? (x) - (y) : (x) - (y) + mo) int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif cin >> n; for (int i = 1; i <= n; i++) scanf("%d",&A[i]); sort(A + 1,A + n + 1); for (int i = 1; i <= n; i++) pre[i] = Add(pre[i - 1],A[i]); for (int i = n; i; i--) suf[i] = Add(suf[i + 1],A[i]); for (int i = 1,tmp = 1; i < n; i++) { Ans = Add(Ans,Mul(tmp,Dec(suf[1 + i],pre[n - i]))); tmp = Add(tmp,tmp); } cout << Ans << endl; return 0; }这是一道交互题 Noora 和 Leha 一起去一家餐馆吃饭 这家餐馆一共有 n 种菜，而Noora点了其中 k 道 为了打发上菜前的无聊时间，他们决定玩一个游戏 每次，Leha提问两个数字 x,y(1≤x,y≤n) 然后 Noora 会从他点的 k 道菜中选择两道a,b满足 |x−a| 与 |y−b| 都是所有可行结果中最小的 此时，若 |x−a|≤|y−b| ， Noora 将会回答 TAK 否则是 NIE Leha 必须在不超过 60 次提问内确定 k 道菜中的任意两道是什么 2≤k≤n≤105
考虑如何确定一道菜 假设区间 [l,r] 中至少存在一道菜 初始令 l=1,r=n ，则条件必定符合 每次，取 l,r 的终点记作 mid 做一次询问 (mid,mid+1) 如果回答为 TAK ，那么 [l,mid] 一定至少存在一道菜 否则 [mid+1,r] 一定至少存在一道菜 那么就能将问题递归到 [l,mid] 或者是 [mid+1,r] 解决 有个显然的性质，当问题被递归以后，选择来回答的菜，一定在区间内 因为如果选一道区间外的菜，明显就违背选择原则了 那么，这样一直递归下去，在 O(logn) 的时间就能确定第一道菜 假设这道菜的位置为 x ，那么对(1,x−1)或者 (x+1,n) 也能用这个策略 因为每次总是选择区间内的菜更优 不过 (1,x−1) 与 (x+1,n) 中可能有一个区间根本没有菜 不过多做一次询问也就能确定了 总得询问次数不超过 O(3logn) 可以通过
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k; char s[30]; bool Query(int x,int y) { printf("1 %d %d\n",x,y); fflush(stdout); scanf("%s",s); return s[0] == 'T' ? 1 : 0; } int Check(int l,int r) { while (r - l > 1) { int mid = l + r >> 1; bool ret = Query(mid,mid + 1); if (ret) r = mid; else l = mid; } return Query(l,r) ? l : r; } int main() { cin >> n >> k; int p1 = Check(1,n),p2; if (p1 > 1) { p2 = Check(1,p1 - 1); bool ret = Query(p2,p1); if (ret) { printf("2 %d %d\n",p1,p2); fflush(stdout); return 0; } } p2 = Check(p1 + 1,n); printf("2 %d %d\n",p1,p2); fflush(stdout); return 0; }有一个 109∗109 的矩阵，记第 x 行y列的元素为 (x,y) (x,y) 的值，定义为所有 (i,y),(x,j)(1≤i<x,1≤j<y) 元素里最小的未出现过的正整数 为了方便理解，这是前 5×5 的矩阵 现在，有 q 次询问，每次是询问一个子矩形内不超过k的数字的和 1≤q≤104,1≤k≤2∗109,1≤x1≤x2≤109,1≤y1≤y2≤109
先给出一个结论，位于 (x,y) 的数字为 ((x−1)⨁(y−1))+1 证明的话，考虑将矩阵的行和列重新从 0 开始标号，然后每个位置减去1 那么现在只需要证明 (x,y) 上的数字等于 x⨁y 就行了 可以考虑使用归纳法证明，位置 (0,0) 显然是成立的 对于位置 (x,y) ，假设所有处于它左方和上方的位置都成立 按照定义证明， (x,y) 上的数字为 x⨁y 则所有 (i,y),(x,j)(1≤i<x,1≤j<y) 的元素包含了 [0,x⨁y) 内的所有整数 并且这些元素没有一个等于 x⨁y 后一条比较容易证明，因为每个 (i,y) 肯定是两两不同的 同理对于每个 (x,j) 也是，所以没有一个等于 x⨁y 对于前一条，任取一个数 z∈[0,x⨁y) 因为 z<x⨁y ，所以，若取一个最大的 k ，满足z和 x⨁y 在这一位上不同 一定是 z 这一位上为0而 x⨁y 这一位上为1 那么在这一位上，一定是 x,y 中一个为 0 另一个为1 不妨假设这个 1 来自于x 取一个 a ，为x上这一位为 0 只需要对于a，将第 k 位以后的数字调整 使得找到a0⨁y=z就行了 这样的 a0 一定是存在的 因为第 k 位小于x，那么这个 a0 一定小于 x 于是就证明了这个结论 那么对于子矩形求和，可以利用容斥原理拆成四个矩形的二维前缀和 这样做的好处是每个矩形的求和的坐标选择范围都是0开始的连续一段 那么就定义状态 f[i][j][k][l] 表示 dp 到第 i 位，是否贴着x,y,k三维，数字的和 同理定义状态 g[i][j][k][l] 类似，不过表示方案数 剩下的就是一个数位 dp 的问题了
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int T = 31; const int N = 32; typedef long long LL; const LL mo = 1000000007; int q,mi[N],f[N][8],g[N][8]; #define Mul(x,y) (1LL * (x) * (y) % mo) #define Add(x,y) ((x) = (x) + (y) < mo ? (x) + (y) : (x) + (y) - mo) #define Dec(x,y) ((x) = (x) - (y) >= 0 ? (x) - (y) : (x) - (y) + mo) #define Check(a,b,c,d) (((a) & (b)) ? (((c) & (d)) ? 1 : 0) : 1) inline int Query(int x,int y,int k) { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); --x; --y; --k; f[T][7] = 1; for (int i = T; i; i--) for (int j = 0; j < 8; j++) { if (!f[i][j] && !g[i][j]) continue; int ta = Check(j,4,x,mi[i - 1]); int tb = Check(j,2,y,mi[i - 1]); int tc = Check(j,1,k,mi[i - 1]); for (int a = 0; a <= ta; a++) for (int b = 0; b <= tb; b++) { if ((a ^ b) > tc) continue; int nex = j; if (a < ta) nex &= 3; if (b < tb) nex &= 5; if ((a ^ b) < tc) nex &= 6; Add(f[i - 1][nex],f[i][j]); Add(g[i - 1][nex],g[i][j]); if (a ^ b) Add(g[i - 1][nex],Mul(f[i][j],mi[i - 1])); } } int ret = 0; for (int i = 0; i < 8; i++) Add(ret,g[0][i]),Add(ret,f[0][i]); return ret; } inline void Solve() { int r1,c1,r2,c2,k; scanf("%d%d%d%d%d",&r1,&c1,&r2,&c2,&k); int Ans = Query(r2,c2,k); if (c1 > 1) Dec(Ans,Query(r2,c1 - 1,k)); if (r1 > 1) Dec(Ans,Query(r1 - 1,c2,k)); if (r1 > 1 && c1 > 1) Add(Ans,Query(r1 - 1,c1 - 1,k)); printf("%d\n",Ans); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif cin >> q; mi[0] = 1; for (int i = 1; i < 31; i++) mi[i] = mi[i - 1] * 2; while (q--) Solve(); return 0; }Leha 和 Noora 打算去一些村庄游玩 一共有 n 个村庄，但是出于一些原因，这些村庄并不总是开放的 具体的，编号为i的村庄，只在 [li,ri] 这几天开放参观 而他们两个人一天只能去一个村庄参观 于是，他们想要选择一个参观序列 x1,x2,x3,…,xk 满足 ∀1≤i<k,xi<xi+1 并且有办法把这些村庄都参观一遍 Leha and Noora 当然是想参观尽可能多的村庄了 所以他们想知道，这个序列最长能是多少，或者说最多参观多少村庄
定义状态 f[i][j] 为，对于前 i 个村庄，最早需要多少天，能参观j个村庄 如果状态非法，那就直接赋值 +∞ 当 i 固定的时候，显然，f[i][j]是单调递增的 因此转移方程就可以暴力写了 f[i][j]=maxf[i−1][j−1]<ri(f[i−1][j−1]+1,li) 于是，对于 f[i] 的更新，找出最小的 x ，使得f[i−1][x]≥li 再找出最大的 y ，使得f[i−1][y]<ri 那么这一整段都可以作转移 f[i−1][k−1]+1→f[i][k] 特别的， f[i][x]=li 那么就等于有两类转移，区间修改，单点插入 这些都可以用 splay 直接解决 那么，就直接 splay 优化 dp 就行了，复杂度 O(nlogn) 写的时候出了点小偏差。。忘了断裂合并操作如何保证均摊复杂度结果真被卡了一发 如果一个 splay 要在位置 x,x+1 处断开 那么就先把 x 转到根然后断裂就是了
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int INF = ~0U>>1; const int maxn = 6E5 666; int n,Ans,cnt,fa[maxn],key[maxn],siz[maxn],Mark[maxn],ch[maxn][2],stk[maxn]; #define maintain(x) (siz[(x)] = 1 siz[ch[(x)][0]] siz[ch[(x)][1]]) inline void pushdown(int x) { if (!Mark[x]) return; key[x] = Mark[x]; if (ch[x][0]) Mark[ch[x][0]] = Mark[x]; if (ch[x][1]) Mark[ch[x][1]] = Mark[x]; Mark[x] = 0; } inline void rotate(int x) { int y = fa[x],z = fa[y]; int d = ch[y][0] == x ? 0 : 1; ch[y][d] = ch[x][d^1]; if (ch[x][d^1]) fa[ch[x][d^1]] = y; ch[x][d^1] = y; fa[y] = x; maintain(y); maintain(x); fa[x] = z; if (z) ch[z][ch[z][1] == y] = x,maintain(z); } inline void splay(int x) { int tp = 0; for (int z = x; z; z = fa[z]) stk[ tp] = z; while (tp) pushdown(stk[tp--]); for (int y = fa[x]; y; rotate(x),y = fa[x]) if (fa[y]) rotate((ch[y][0] == x) ^ (ch[fa[y]][0] == y) ? x : y); } inline int Lower_Bound(int x,int k) { if (!x) return 0; pushdown(x); if (key[x] < k) return Lower_Bound(ch[x][1],k); else { int ret = Lower_Bound(ch[x][0],k); return ret ? ret : x; } } inline int Find(int x,int k) { pushdown(x); int now = siz[ch[x][0]] 1; if (now == k) return x; if (now > k) return Find(ch[x][0],k); else return Find(ch[x][1],k - now); } inline void Search(int x,int k) { if (!x) return; pushdown(x); int now = siz[ch[x][0]] 1; if (key[x] != INF) Ans = max(Ans,k now); Search(ch[x][0],k); Search(ch[x][1],k now); } inline int Build(int l,int r) { if (l > r) return 0; int mid = l r >> 1; ch[mid][0] = Build(l,mid - 1); ch[mid][1] = Build(mid 1,r); if (ch[mid][0]) fa[ch[mid][0]] = mid; if (ch[mid][1]) fa[ch[mid][1]] = mid; maintain(mid); return mid; } inline int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret * 10 ch - '0',ch = getchar(); return ret; } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif n = getint(); for (int i = 2; i <= n 2; i ) key[i] = INF; Build(1,n 2); cnt = n 2; for (int i = 1; i <= n; i ) { int l = getint(),r = getint(); splay(1); int x = Lower_Bound(1,l),y = Lower_Bound(1,r); if (x == y) splay(x),key[x] = l; else { splay(x); int rkx = siz[ch[x][0]] 1; splay(1); int A = Find(1,rkx - 1); splay(A); fa[ch[A][1]] = 0; ch[A][1] = 0; maintain(A); splay(y); fa[ch[y][0]] = 0; ch[y][0] = 0; int B = ch[y][1]; fa[B] = 0; ch[y][1] = 0; splay(x); Mark[x]; fa[x] = cnt; key[cnt] = l; ch[cnt][1] = x; maintain(cnt); int C = Find(cnt,siz[cnt]); splay(C); ch[A][1] = C; fa[C] = A; maintain(A); ch[C][1] = B; fa[B] = C; maintain(C); } } splay(1); Search(1,0); cout << Ans - 1 << endl; return 0; }有一棵有n个节点的树，第 i 个节点上写着数字ai 保证所有节点的数字组成一个 1→n 的排列 定义点对 (u,v) 的权值为 φ(auav)×d(u,v) 其中 d(u,v) 为 u,v 两点在树上的距离 随机从树上选择两点 u,v(u≠v) 请问得到的权值期望是多少？输出这个值对 109+7 取模的结果即可 2≤n≤2∗105 注意 (u,v) 与 (v,u) 算作不同点对
首先对于 φ(auav) 不太好求 注意到 φ(auav)=φ(au)φ(av)gφ(g),g=gcd(au,av) 证明的话，直接用 φ 的展开式就行了 对这棵树进行点分治，每次取出重心，记为 o φ(auav)×d(u,v)=φ(au)φ(av)gφ(g)(Lu Lv)=φ(av)gφ(g)φ(au)Lu φ(au)gφ(g)φ(av)Lv 其中 Lu 为 u 到o的距离 点分治的时候只需要考虑每一层跨过重心的路径 所以对于每个点 u 只需要知道其它子树中∑φ(av)gφ(g)的值就行了 记 sumg=∑gcd(au,av)=gφ(av) 于是 ∑φ(av)gφ(g)=∑g|ausumggφ(g) 那么最后的问题是 sumg 的求法了 记 sumphig=∑g|avφ(av) 显然有 sumg=sumphig−∑g|x,x≠g,x|ausumx 记 f(n) 为 n 的约数的个数 可以用积分证明，此时的复杂度约为O((∑ni=1nif(i))logn)≈O(nlog3n) 最后的瓶颈是 sumg 的求法太慢了 注意到 sumg 总是能写成 sumphig 的和 那么如果能找到一组系数，使得 ∑g|ausumggφ(g)=∑g|aucau[g]sumphig 原问题就能在 O(nlog2n) 的时间解决了 对于 c 数组的计算，枚举x=1→n 记 p 为x的最小质因数， α 为 p 的幂次，q=xpα 枚举 x 的每一个因数z，若 p|z ，则 cp[z]=cq[zp]p−1 否则， cp[z]=cq[z] 边界显然， c1[1]=1 公式的证明可以采用数学归纳法
#include<iostream> #include<cstdio> #include<vector> #include<stack> #include<queue> #include<cstring> #include<algorithm> //#include<ctime> using namespace std; typedef long long LL; const int maxn = 2E5 + 5; const LL mo = 1000000007; int n,m,O,Max,cnt,tot,Cnt,phi[maxn],A[maxn],Fac[maxn],mu[maxn],pri[maxn] ,inq[maxn],dis[maxn],Inv[maxn],siz[maxn],sumphi[maxn],vis[maxn]; bool not_pri[maxn],Huge[maxn]; LL Ans; queue <int> Q; stack <int> stk; vector <int> v[maxn],d[maxn],c[maxn]; #define Mul(x,y) (1LL * (x) * (y) % mo) #define max(a,b) ((a) > (b) ? (a) : (b)) #define Add(x,y) ((x) + (y) < mo ? (x) + (y) : (x) + (y) - mo) inline int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret * 10 + ch - '0',ch = getchar(); return ret; } int ksm(int x,int y) { int ret = 1; for (; y; y >>= 1) { if (y & 1) ret = Mul(ret,x); x = Mul(x,x); } return ret; } inline void Clear() { while (!stk.empty()) sumphi[stk.top()] = 0,stk.pop(); } inline void Insert(int x) { int y = A[x]; for (int i = 0; i < d[y].size(); i++) { int now = d[y][i]; sumphi[now] = Add(sumphi[now],phi[y]); if (vis[now] != cnt) vis[now] = cnt,stk.push(now); } } inline void Dfs2(int x,int tot,int from) { int ma = 0; siz[x] = 1; for (int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if (to == from || Huge[to]) continue; Dfs2(to,tot,x); siz[x] += siz[to]; ma = max(ma,siz[to]); } ma = max(ma,tot - siz[x]); if (ma < Max) Max = ma,O = x; } inline void BFS1(int x) { dis[x] = 1; inq[x] = ++Cnt; Q.push(x); while (!Q.empty()) { int k = Q.front(),y = A[k]; Q.pop(); LL sum = 0; for (int i = 0; i < d[y].size(); i++) sum += 1LL * c[y][i] * sumphi[d[y][i]]; sum %= mo; Ans += Mul(sum,Mul(phi[y],dis[k])); for (int i = 0; i < v[k].size(); i++) { int to = v[k][i]; if (inq[to] == Cnt || Huge[to]) continue; inq[to] = Cnt; dis[to] = dis[k] + 1; Q.push(to); } } Ans %= mo; } inline int BFS2(int x) { int ret = 0; Q.push(x); inq[x] = ++Cnt; while (!Q.empty()) { int k = Q.front(); Q.pop(); ++ret; Insert(k); for (int i = 0; i < v[k].size(); i++) { int to = v[k][i]; if (inq[to] == Cnt || Huge[to]) continue; inq[to] = Cnt; Q.push(to); } } return ret; } inline void Dfs1(int x,int tot) { Max = maxn; Dfs2(x,tot,0); int o = O; Huge[o] = 1; ++cnt; Insert(o); for (int i = 0; i < v[o].size(); i++) { int to = v[o][i]; if (Huge[to]) continue; BFS1(to); BFS2(to); } Clear(); ++cnt; for (int i = v[o].size() - 1; i >= 0; i--) { int to = v[o][i]; if (Huge[to]) continue; BFS1(to); siz[to] = BFS2(to); } Clear(); for (int i = 0; i < v[o].size(); i++) { int to = v[o][i]; if (Huge[to]) continue; Dfs1(to,siz[to]); } } void Pre_Work() { n = getint(); Fac[0] = 1; for (int i = 1; i <= n; i++) A[i] = getint(),m = max(m,A[i]); for (int i = 1; i <= m; i++) Fac[i] = Mul(Fac[i - 1],i); Inv[m] = ksm(Fac[m],mo - 2); for (int i = m - 1; i; i--) Inv[i] = Mul(Inv[i + 1],i + 1); for (int i = m; i; i--) Inv[i] = Mul(Inv[i],Fac[i - 1]); for (int i = 1; i < n; i++) { int x = getint(),y = getint(); v[x].push_back(y); v[y].push_back(x); } phi[1] = mu[1] = 1; for (int i = 2; i <= m; i++) { if (!not_pri[i]) pri[++tot] = i,phi[i] = i - 1,mu[i] = -1; for (int j = 1; j <= tot; j++) { int Nex = i * pri[j]; if (Nex > n) break; not_pri[Nex] = 1; if (i % pri[j] == 0) { phi[Nex] = phi[i] * pri[j]; mu[Nex] = 0; break; } mu[Nex] = -mu[i]; phi[Nex] = phi[i] * (pri[j] - 1); } } for (int i = 1; i <= m; i++) d[i].push_back(1); for (int i = 2; i <= m; i++) { if (!mu[i]) continue; for (int j = i; j <= m; j += i) d[j].push_back(i); } c[1].push_back(1); for (int i = 2; i <= m; i++) { int q = i,p = d[i][1],p1 = 0,p3 = 0; while (q % p == 0) q /= p; for (int j = 0; j < d[i].size(); j++) { int z = d[i][j]; if (z % p != 0) { while (d[q][p1] != z) ++p1; c[i].push_back(c[q][p1]); } else { int now = z / p,tmp; while (d[q][p3] != now) ++p3; tmp = Mul(Inv[p - 1],c[q][p3]); c[i].push_back(tmp); } } } } int main() { /*#ifdef DMC freopen("DMC.txt","r",stdin); #else freopen("sm.in","r",stdin); freopen("sm.out","w",stdout); #endif*/ Pre_Work(); Dfs1(1,n); cout << Mul(Mul(2,Ans),Mul(Inv[n],Inv[n - 1])) << endl; //cerr << (double)(clock()) / CLOCKS_PER_SEC << endl; return 0; }具体的复杂度与公式证明限于篇幅就不介绍了 (主要是我写过一遍，太懒不想再写了) 有兴趣的朋友欢迎向我发邮件索要。。。就是 QQ 邮箱啦 关于 E 题，发现了一个使用虚树做法O(nlogn)的大神额
