T1：
考场卡点在于如何采用根号算法求解，试图推性质，利用根号左侧数据更新根号右侧数据
开方即可，然而当数据存在指数为奇数的质因子时无法进行计算
正解为整除分块，事实上大多数数论根号算法都是数论分块
考虑如何对问题所求进行转化，对于2^n，能够想到可以类比为子集枚举，那么发现，问题等价于
对于1~n内质因数进行子集枚举，于是考虑转化为求解子集贡献，设子集为k，那么问题等价于求
sigma u^2(k) * n / k，u^2考虑莫比乌斯函数的定义，在质因数集含偶指数时为0，不含则为(-1)^k，
k为集合大小，那么我们需要的是对于任意不含偶指数质因子集贡献为1，于是需要魔改u函数，平方即可
上述式子需要杜教筛进行优化，数论分块的话发现难以进行，考虑转换思路，问题等价于求解
sigma u^2(d)（d | n） = sigma sigma u(d)（d | n && k^2 | d）（证明采用二项式定理，考虑u函数意义即可），
和式变换枚举d得到sigma u(d) * sigma（k^2 | d）n / d
设d = k^2 * i，得到 sigma u(d) sigam n / (k * k * i)，于是对后者数论分块即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I mod = 1e9 + 7;
20 LL n,ans;
21 I cnt,prime[78500];
22 B not_prime[1000005];
23 I u[1000005],pre[1000005];
24 inline LL read () {
25 LL x(0),y(1); C z(getchar());
26 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
27 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
28 return x * y;
29 }
30 inline V Max (I &a,I b) { a = a > b ? a : b; }
31 inline V Min (I &a,I b) { a = a < b ? a : b; }
32 inline I max (I a,I b) { return a > b ? a : b; }
33 inline I min (I a,I b) { return a < b ? a : b; }
34 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
35 inline I abs (I a) { return a >= 0 ? a : -a; }
36 inline P operator + (const P &a,const P &b) {
37 return MP (a.a + b.a,a.b + b.b);
38 }
39 inline P operator - (const P &a,const P &b) {
40 return MP (a.a - b.a,a.b - b.b);
41 }
42 signed main () {
43 FP (elegant.in), FC (elegant.out);
44 n = read ();
45 I t (ceil (sqrt (n)));
46 u[1] = pre[1] = 1;
47 for (I i(2);i <= t; ++ i) {
48 if (!not_prime[i]) prime[cnt++] = i, u[i] = -1;
49 for (I j(0);j < cnt && i * prime[j] <= t; ++ j) {
50 not_prime[i * prime[j]] = 1;
51 if (i % prime[j] == 0) break;
52 u[i * prime[j]] = -u[i];
53 }
54 pre[i] = pre[i - 1] + u[i];
55 }
56 I w,s;
57 for (I l(1),r;l <= t;l = r + 1) {
58 if (n / (l * l) == 0) break;
59 r = sqrt (n / (n / (l * l))), w = n / (l * l), s = 0;
60 for (I a(1),b;a <= w;a = b + 1) {
61 b = w / (w / a);
62 (s += (b - a + 1) * (w / a) % mod) %= mod;
63 }
64 (ans += (pre[r] - pre[l - 1]) * s % mod) %= mod;
65 }
66 printf ("%lld\n",(ans + mod) % mod);
67 }
View Code
T2：
set暴力维护即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I N = 1e5 + 3, inf = 1e9;
20 I typ,n,m,c,p,ans;
21 I tot,head[N],to[N << 1],nxt[N << 1];
22 I cnt,dfn[N],f[N],t[N],s[N],size[N],d[N];
23 multiset <I> g[N];
24 inline I read () {
25 I x(0),y(1); C z(getchar());
26 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
27 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
28 return x * y;
29 }
30 inline V Max (I &a,I b) { a = a > b ? a : b; }
31 inline V Min (I &a,I b) { a = a < b ? a : b; }
32 inline I max (I a,I b) { return a > b ? a : b; }
33 inline I min (I a,I b) { return a < b ? a : b; }
34 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
35 inline I abs (I a) { return a >= 0 ? a : -a; }
36 inline P operator + (const P &a,const P &b) {
37 return MP (a.a + b.a,a.b + b.b);
38 }
39 inline P operator - (const P &a,const P &b) {
40 return MP (a.a - b.a,a.b - b.b);
41 }
42 inline V found (I x,I y) {
43 to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
44 to[++tot] = x, nxt[tot] = head[y], head[y] = tot;
45 }
46 V Dfs1 (I x,I father) {
47 f[x] = father, size[x] = 1;
48 for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != father) {
49 d[y] = d[x] + 1, Dfs1 (y,x), size[x] += size[y];
50 if (size[y] > size[s[x]]) s[x] = y;
51 }
52 }
53 V Dfs2 (I x,I top) {
54 dfn[x] = ++cnt, t[x] = top;
55 if (!s[x]) return ; Dfs2 (s[x],top);
56 for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != f[x] && y != s[x])
57 Dfs2 (y,y);
58 }
59 inline I LCA (I x,I y) {
60 while (t[x] != t[y]) dfn[x] < dfn[y] ? y = f[t[y]] : x = f[t[x]];
61 return dfn[x] < dfn[y] ? x : y;
62 }
63 signed main () {
64 FP (yygq.in), FC (yygq.out);
65 typ = read (), n = read ();
66 for (I i(1);i < n; ++ i)
67 found (read (), read ());
68 Dfs1 (1,0), Dfs2 (1,1);
69 m = read ();
70 while (m -- ) {
71 I tp (read ()), x (read () ^ (ans * typ));
72 if (tp == 1) {
73 g[p + 1] = g[c]; c = ++ p;
74 if (g[p].find (x) == g[p].end ()) g[p].insert (x); else g[p].erase (g[p].find (x));
75 }
76 if (tp == 2) {
77 ans = inf;
78 if (x > n) { puts ("1000000000"); continue; }
79 for (auto y : g[c])
80 Min (ans,d[x] + d[y] - d[LCA (x,y)] * 2);
81 printf ("%d\n",ans);
82 }
83 if (tp == 3 && x <= p) c = x;
84 }
85 }
View Code
T3：
考虑根据题意，设f[i][j]表示i个数，j次交换方案数，考虑dp转移，首先第i个数不进行交换
直接继承上一次状态为f[i][j] += f[i - 1][j]，第二种情况为第i个数进行交换，考虑交换对象有
i - 1种选择，于是有转移f[i][j] += f[i - 1][j - 1] * (i - 1)
考虑优化dp，发现本题dp的本质与输入的n与k并不相关，考虑其数学原理，利用表格法
将dp的转移路径在草纸上画出，可以发现，dp转移最多进行k次，每次转移项数加1并且次数加1
于是根据自然数平方和定理每次转移由项数与次数分别进次，那么最终f[n][k]即为不超过2 * k - 1
次多项式，最终要求前缀和，那么即为2 * k次多项式，拉格朗日插值求出前2 * k项前缀和即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I mod = 1e9 + 7;
20 I n,k,ans,f[2][6005],y[6005];
21 inline I read () {
22 I x(0),y(1); C z(getchar());
23 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
24 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
25 return x * y;
26 }
27 inline V Max (I &a,I b) { a = a > b ? a : b; }
28 inline V Min (I &a,I b) { a = a < b ? a : b; }
29 inline I max (I a,I b) { return a > b ? a : b; }
30 inline I min (I a,I b) { return a < b ? a : b; }
31 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
32 inline I abs (I a) { return a >= 0 ? a : -a; }
33 inline P operator + (const P &a,const P &b) {
34 return MP (a.a + b.a,a.b + b.b);
35 }
36 inline P operator - (const P &a,const P &b) {
37 return MP (a.a - b.a,a.b - b.b);
38 }
39 inline I fp (I a,I b) {
40 I ans (1);
41 for (; b ;b >>= 1, a = a * a % mod)
42 if (b & 1) ans = ans * a % mod;
43 return ans;
44 }
45 signed main () {
46 FP (guess.in), FC (guess.out);
47 n = read (), k = read ();
48 for (I i(1);i < 6005; ++ i) {
49 y[i] = f[i & 1][0] = 1;
50 for (I j(1);j < 6005 && j <= k; ++ j)
51 f[i & 1][j] = (f[i - 1 & 1][j] + (i - 1) * f[i - 1 & 1][j - 1]) % mod, y[i] = (y[i] + f[i & 1][j]) % mod;
52 if (i == n) printf ("%lld\n",y[i]), exit (0);
53 }
54 for (I i(1);i < 6005; ++ i) {
55 I pro1 (y[i]), pro2 (1);
56 for (I j(1);j < 6005; ++ j) if(j != i)
57 pro1 = pro1 * (n - j) % mod, pro2 = pro2 * (i - j) % mod;
58 ans = (ans + pro1 * fp (pro2,mod - 2) % mod) % mod;
59 }
60 printf ("%lld\n",(ans + mod) % mod);
61 }
View Code