T1：
原题，树形DP+贪心即可
代码如下：
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 LL long long
8 #define P pair<I,I>
9 #define MP make_pair
10 #define fir first
11 #define sec second
12 const I N = 1e6 + 3;
13 I n,f[N],MA[N],dp[N];
14 I tot,head[N],to[N << 1],nxt[N << 1];
15 P a[N];
16 inline I read() {
17 I x(0),y(1); C z(getchar());
18 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
19 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
20 return x * y;
21 }
22 inline V found (I x,I y) {
23 to[++tot] = y, nxt[tot] = head[x], head[x] = tot;
24 to[++tot] = x, nxt[tot] = head[y], head[y] = tot;
25 }
26 inline V Max (I &a,I b) { a = a > b ? a : b; }
27 inline V Min (I &a,I b) { a = a < b ? a : b; }
28 inline I max (I a,I b) { return a > b ? a : b; }
29 inline I min (I a,I b) { return a < b ? a : b; }
30 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
31 V Dfs (I x,I deep) {
32 I cnt(0);
33 for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != f[x])
34 Dfs (y,deep + 1), Max (MA[x],MA[y] + 1);
35 for (I i(head[x]),y(to[i]); i ;i = nxt[i],y = to[i]) if (y != f[x])
36 a[cnt++] = MP (MA[y],y);
37 if (!cnt) return (V)(dp[x] = deep);
38 sort (a,a + cnt);
39 for (I i(1);i < cnt; ++ i)
40 if (a[i - 1].fir + 1 < deep)
41 dp[a[i].sec] -= deep - a[i - 1].fir - 1;
42 else
43 break;
44 for (I i(0);i < cnt; ++ i)
45 dp[x] += dp[a[i].sec];
46 }
47 signed main () {
48 n = read();
49 for (I i(2);i <= n; ++ i)
50 f[i] = read(), found (f[i],i);
51 Dfs (1,0);
52 printf ("%d\n",dp[1]);
53 }
View Code
T3：
首先感性理解的话，对于每种情况出现概率相同是显然的
考虑证明：设出现的情况为a1...an
那么对于ai其需要的1的个数为(ai - 1)，显然的可重集排列m! / ∏(ai-1)!
接下来考虑对于该情况出现的概率，考虑首先比较显然的是总情况数为n*(n+1)*...*(n+m-1)
那么考虑对于该情况，总的出现次数为∏(ai-1)!（将每个集合进行排列即可）
于是对于每种情况出现概率即为m! / ∏(ai-1)! * ∏(ai-1)! / n*(n+1)*...*(n+m-1)
接下来首先考虑如何计算前r大数字之和，考虑若枚举前r大数字必然超时，如何消去不同数字的特性
转化为相同的计算结构，比较套路的做法为考虑1的贡献，对于1会作出贡献当且仅当其属于最大的r个数
于是考虑转化问题为计算最大的r个数中有多少个1，考虑类似与素因子筛，我们可以构造出一种筛法
使得仅满足一定条件的1会被计算，于是设f(i,j)表示对于所有情况中至少有i个数大于j的情况数
那么枚举i的过程相当于枚举当前在计算第i大的数的贡献，枚举j的过程相当与枚举第i大的数的所有可能情况
当且仅当第i大的数大于j时会作出一次贡献，于是当j枚举结束时即为所有情况中第i大的数所能造成的贡献
接下来考虑如何计算f(i,j)，观察函数形式，比较套路的设g(i,j)为恰好有i个数大于j
那么显然f函数可以转化为g函数后缀和的形式，考虑如何计算g函数，比较显然的容斥原理（奇加偶减）
g(i,j) = sigma(k)(-1)^(k-i) * C(n,k) * C(k,i) * C(n - 1 - m - j*k,n - 1)
首先枚举至少有k个数大于j，然后C(n,k)钦定k个数，C(k,i)为其对g(i,j)的贡献次数，C(n - 1 - m - j*k,n - 1)为可重集组合
因为要满足至少有k个数大于j，于是首先给每个数分配j，剩余的数随意分配即可
因为要保证合法，所以i*j<=m,j*k<=m
时间复杂度sigma(m/i)^2
代码如下：
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 LL long long
8 #define P pair<I,I>
9 #define MP make_pair
10 #define fir first
11 #define sec second
12 const I N = 5e3 + 3;
13 const I mod = 1e9 + 7;
14 I n,m,Inv,ans,J[N << 1],Y[N << 1],g[N][N];
15 inline I read() {
16 I x(0),y(1); C z(getchar());
17 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
18 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
19 return x * y;
20 }
21 inline V Max (I &a,I b) { a = a > b ? a : b; }
22 inline V Min (I &a,I b) { a = a < b ? a : b; }
23 inline I max (I a,I b) { return a > b ? a : b; }
24 inline I min (I a,I b) { return a < b ? a : b; }
25 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
26 inline I fp (I a,I b) { I ans(1);
27 for (; b ;b >>= 1, a = 1ll * a * a % mod)
28 if (b & 1) ans = 1ll * ans * a % mod;
29 return ans;
30 }
31 inline I _C (I n,I m) {
32 return 1ll * J[n] * Y[m] % mod * Y[n - m] % mod;
33 }
34 signed main () {
35 n = read(),m = read(); J[0] = Y[0] = 1;
36 for (I i(1);i <= n + m; ++ i) J[i] = 1ll * J[i - 1] * i % mod;
37 Y[n + m] = fp (J[n + m],mod - 2);
38 for (I i(n + m - 1); i; -- i) Y[i] = 1ll * Y[i + 1] * (i + 1) % mod;
39 Inv = fp (_C(n + m - 1,n - 1),mod - 2);
40 for (I i(1);i <= n; ++ i)
41 for (I j(1),tmp1(m / i);j <= tmp1; ++ j)
42 for (I k(i),tmp2(m / j);k <= tmp2; ++ k)
43 (g[i][j] += (k - i & 1 ? -1ll : 1ll) * _C(n,k) * _C(k,i) % mod * _C(n + m - j * k - 1,n - 1) % mod) %= mod;
44 for (I j(1);j <= m; ++ j)
45 for (I i(m / j);i >= 1; -- i)
46 g[i][j] = (g[i][j] + g[i + 1][j]) % mod;
47 for (I i(1);i <= n; ++ i) {
48 for (I j(m / i);j >= 1; -- j)
49 ans = (ans + g[i][j]) % mod;
50 printf ("%lld\n",(1ll * ans * Inv % mod + i + mod) % mod);
51 }
52 }
View Code
Update：补坑：关于反演系数的计算
二项式反演中集合计数的做法一直有所困惑，根据定义：
f为集合元素恰好为i的方案数，g为集合元素至少为i的方案数
那么显然f为g函数的后缀和，然而题解做法给出的确是组合系数
当时给出的理解为因为g函数的计算过程中存在问题那么这种反演系数恰好能修正这种问题
接下来给出看起来更合理的解释：
考虑事实上反演的原理与正确性都是相同的，原因在于函数计算方式的不同，对于本题而言
f函数直接定义为g函数的后缀，显然具有正确性，那么这要求g函数的计算必须完全准确
考虑集合计数，显然可以发现g函数的计算存在重复，然而并不影响结果，原因就在于计算方式
其f函数定义g函数的贡献时是考虑每组数的贡献，这种定义方式本身就存在问题，换言之，
这种定义方式与计算方式一一对应，因此，观察两道题的特点就在于此
集合计数是g函数利用公式直接简洁计算，而总结结果f时利用容斥计算
而本题总结结果时直接利用g后缀和计算f，而计算g时需要容斥计算
因此这两种方式本质上是相同的，需要注意的只是在不同情况下选择不同方法，定义的计算方式要一一对应