挂分比得分多。。。
挂了 145，得了 107。。。
T1 seq 思路分析 我们只考虑前 \(\lfloor \frac{n}{2} \rfloor\) 个数，这样一来， \(a,b,c\) 三个序列就是独立的。要求的是 \(a,b\) 两个序列的方案总数，并且满足 \(a_i \operatorname{xor} b_i = c_i,\sum{\operatorname{popcount}(c_i)=k}\) 。
如果直接计算 \(a, b\) ，显然 \(c\) 不好满足。但是异或是可逆的，对于一个给定的 \(a\) ，确定了 \(c\) 就相当于确定了 \(b\) 。所以就是求 \(a,c\) 两个序列的总数，并要求 \(\sum{\operatorname{popcount}(c_i)}=k\) 。这就很简单了，因为 \(a,c\) 互不干扰。记 \(w=\lfloor\frac{n}{2}\rfloor \times m\) ，\(a\) 一共有 \(w\) 个二进制位，所以有 \(2^w\) 种；\(c\) 可以在 \(w\) 个二进制位中选 \(k\) 个，所以有 \(\operatorname{C}_{w}^{k}\) 个方案。
然后是细节部分。挂分原因一是 \(w\) 很大，在处理组合数算阶乘的时候，必须要将 \(i\) 先取模再乘再取模；另外是当 \(n\) 是奇数的时候，中间那个位置选什么数都没关系，答案要再乘上 \(2^m\) 。
code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <bits/stdc++.h> using namespace std;#define FILE_IO namespace io {...};using namespace io;const long long mod = 1e9 + 7 ;long long n, m, k, ans;long long quick_pow (long long x, long long p) if (p == 0 ) return 1LL ; if (p == 1 ) return x; long long res = quick_pow (x, p >> 1 ); (res *= res) %= mod; if (p & 1LL ) (res *= x) %= mod; return res; } long long C (long long n, long long m) if (m > n) return 0LL ; if (m == 0 || m == n) return 1LL ; long long res = 1 ; for (long long i = n; i >= n - m + 1 ; i--) { (res *= (i % mod)) %= mod; } long long tmp = 1 ; for (long long i = 1 ; i <= m; i++) { (tmp *= (i % mod)) %= mod; } return res * quick_pow (tmp, mod - 2 ) % mod; } int main () read (n); read (m); read (k); if (k & 1LL ) { write (0 ); return 0 ; } ans = quick_pow (2 , (n + 1 ) / 2 * m); k >>= 1 ; n >>= 1 ; write (ans * C (n * m, k) % mod); return 0 ; }
T2 connections 思路分析 挂分原因：题目说有向图我存了无向（警钟敲烂）。
而且作为 juruo，tarjan 算法也写挂了。
其实根本不用求什么环。由于题目已经保证了双连通，所以从 \(1\) 出发一定能访问所有点，而且由于所有点都能访问 \(1\) ，所以反图上 \(1\) 一定也能访问所有点。在正反图上从 \(1\) 出发各跑一次 dfs，正图上经过的边就能保证 \(1\) 到达所有点，反图上经过的边就能保证所有点都到达 \(1\) ，两者结合就能保证整张图双连通，而这最多也只需要 \(2n-2\) 条边，剩下不需要的随意输出 \(m-2n\) 个即可。
AC 代码 code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <bits/stdc++.h> using namespace std;#define FILE_IO namespace io {...};using namespace io;const int maxm = 5e5 + 5 , maxn = 2.5e5 ;int n, m;struct node { int u, v; } e[maxm]; bool vis[maxn], book[maxm];vector<int > graph[maxn], inv_graph[maxn]; void dfs (int u) vis[u] = true ; for (int i : graph[u]) { int v = e[i].u ^ e[i].v ^ u; if (vis[v]) continue ; dfs (v); book[i] = true ; } } void dfs2 (int u) vis[u] = true ; for (int i : inv_graph[u]) { int v = e[i].u ^ e[i].v ^ u; if (vis[v]) continue ; dfs2 (v); book[i] = true ; } } int main () read (n); read (m); for (int i = 1 ; i <= m; i++) { read (e[i].u); read (e[i].v); graph[e[i].u].emplace_back (i); inv_graph[e[i].v].emplace_back (i); } dfs (1 ); memset (vis, 0 , sizeof vis); dfs2 (1 ); int cnt = 0 ; for (int i = 1 ; i <= m; i++) { if (!book[i]) { cnt++; write (i, " \n" [cnt == m - 2 * n]); } if (cnt == m - 2 * n) break ; } return 0 ; }
T3 subseq 思路分析 定义 \(f_i\) 表示从第 \(i\) 位开始匹配，至少需要多少个数才能超过 \(a\) 的匹配范围。有一个显然的贪心结论：\(f_i\) 应该从 \(i\) 之后最后一个首次出现的数转移过来。比如 \(2,1,3,1,2,3\) ，\(f_2\) 之后最后一个首次出现的数是第 \(5\) 位的 \(2\) ，所以 \(f_2 \leftarrow f_5+1\) 。
如何找到“最后一个首次出现的数”呢？用 \(nxt_i\) 表示第 \(i\) 位之后下一个和 \(i\) 取值相同的位置，再对 \(nxt\) 做一个前缀最大值，记为 \(mnxt_i\) ，则“最后一个首次出现的数”就是 \(mnxt_i\) 。其实不需要用到什么队列优化。
这样，从后往前处理出 \(f_i \leftarrow f_{mnxt_i} + 1\) ，剩下的问题就是字典序。
首先 \(f_i=f_1\) 的部分是不用选取的，也是不能选取的。最优的匹配方案应该是从 \(f_i=f_1-1\) 的位置开始选取。 但是如果取到了一个值使得 \(f_i=f_1\) 的部分也有这个值，那么匹配时就会匹配到 \(f_i=f_1\) 的部分，而不会匹配到 \(f_i=f_1-1\) 的部分。所以我们要对满足 \(f_i=f_1\) 的 \(a_i\) 打上标记，然后在 \(f_i=f_1-1\) 的 \(a_i\) 中找到未被标记的最小 \(a_i\) ，这样第一个数就一定满足字典序最小。这时我们就可以发现这样的操作是可以递归的，如果第一位找到了 \(a_x\) ，想找出第二位，就先把 \(x\) 之后满足 \(f_i=f_x\) 的 \(a_x\) 标记掉，再从 \(f_i=f_x-1\) 的位置中找到未被标记的最小 \(a_i\) 。每次都如此，就能构造出答案。
AC 代码 code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 #include <bits/stdc++.h> using namespace std;#define FILE_IO namespace io {...};using namespace io;const int maxn = 1.1e7 + 5 , maxm = 1e6 + 5 ;unsigned int sd,sd2=998244353 ,sd3=114514 ;unsigned int my_rand () sd^=(sd2^sd3),sd2^=sd3+233 ,sd3^=sd*1945 ; return (sd^sd2^sd3^20041025 )+sd*sd2*sd3; } int n,m,a[maxn];int tmp;inline void Swap (int &x,int &y) return ;}void input () read (n); read (m); read (sd); for (int i=1 ;i<=m;i++) for (int j=i;j<=n;j+=m) a[j]=i; for (int i=1 ;i<=1e6 ;i++) Swap (a[my_rand ()%n+1 ],a[my_rand ()%n+1 ]); return ; } bool book[maxm];int nxt[maxn], lst[maxm], mnxt[maxn], f[maxn];int main () input (); for (int i = 1 ; i <= n; i++) { if (!lst[a[i]]) { mnxt[0 ] = max (mnxt[0 ], i); } else nxt[lst[a[i]]] = i; lst[a[i]] = i; } for (int i = 1 ; i <= m; i++) nxt[lst[i]] = n + 1 ; nxt[n + 1 ] = n + 1 ; for (int i = 1 ; i <= n; i++) mnxt[i] = max (mnxt[i - 1 ], nxt[i]); for (int i = n; i >= 0 ; i--) { f[i] = f[mnxt[i]] + 1 ; } write (f[0 ]); for (int i = 0 ; i <= n;) { int j = i + 1 ; for (; f[j] == f[i]; j++) { book[a[j]] = true ; } int val = m + 1 , mi; for (; f[j] == f[i] - 1 ; j++) { if (!book[a[j]] && a[j] < val) { val = a[j], mi = j; } } for (j = i + 1 ; f[j] == f[i]; j++) { book[a[j]] = false ; } write (val, ' ' ); i = mi; if (f[i] == 1 ) { for (int j = i + 1 ; j <= n; j++) book[a[j]] = true ; for (int j = 1 ; j <= m; j++) { if (!book[j]) { write (j); break ; } } break ; } } return 0 ; }
T4 point 思路分析 对于每一个质数 \(p\) ，将是 \(p\) 的倍数的点建出一棵虚树，那么查询实际上就是询问虚树的子树直径。
如何做这个询问呢？既然是子树修改，我们不妨考虑 dfs 序转化成区间修改，用线段树维护。但是线段树会把原本在一个子树中的点分到左右两棵树中，这两部分不一定连续，我们怎么从不连续的部分合并出整棵树的直径呢？
有一个结论。两个点集并的直径的端点一定是原来两个点集直径的端点。
这样就可以维护了。
为了实现修改，我们更改一下线段树的建树方式，不是在虚树的 dfs 序上建线段树，而是在原树的 dfs 序上建线段树，但是动态开点，如果这个点不在虚树中，就不开这个点，相当于建一棵虚线段树。这样，单点修改就是多开一个点。
至于子树修改，如果将所有点新开，必然 MLE + TLE，但是我们发现，子树修改对应到 dfs 序上就是区间修改，而对应到线段树上，就是新开 \(O(\log n)\) 棵完全二叉树 。所以我们可以预先维护一棵所有点都加入的完全二叉树，修改时只要将指针指向完全二叉树中的对应部分，就相当于完成了开点。
时间复杂度 \(O(wq \log n)\) 。（\(w\) 是质因数个数)。