Description

? 給你一棵\(~n~\)個點的樹和一個整數(shù)\(~k~\)。設(shè)為\(~S~\)為樹上某些點的集合，定義\(~f(S)~\)為最小的包含\(~S~\)的聯(lián)通子圖的大小。\(~n~\)個點選\(~k~\)個點一共有\(~C_n^k~\)種方案，請你求出所有方案的\(~f(S)~\)的和， 對\(~924844033~\)取模。

? 求所有\(~k \in [1, ~n]~\)的答案。
看題戳我

Solution

? 首先看到這道題，根本不會快速求\(~f(S)~\)，所以換一個角度，考慮每個點對于答案的貢獻。不難發(fā)現(xiàn)， 對于單獨一個\(~k~\)，一個點\(~u~\)會產(chǎn)生貢獻當且僅當這\(~k~\)個點不全在以\(~u~\)的相鄰節(jié)點為根的子樹中，根據(jù)容斥可以得到一個點對一個\(~k~\)的貢獻為\(~C_n^k - \sum_{v \in {nex_u}} ^{} {C_{siz_v}^k}~\)，觀察這個式子，可以發(fā)現(xiàn)計算總貢獻時每個點的子樹大小會被計算兩次，一個是本身子樹大小\(~siz_u~\)，一個是\(~n - siz_u~\)，而 \(~C_n^k~\)被計算了\(~n~\)次，所以有
\[ Ans_k = n \times {n \choose k} - \sum_{i = 1} ^ n {num_i \times {i \choose k}} \]
? 其中，\(num_i~\)表示子樹大小為\(~i~\)的子樹個數(shù)，這樣已經(jīng)可以卷后半部分了，但是我們想要一個更簡便的式子。

定義一個新的\(~cnt_i~\)表示
\[ cnt_i = \begin{cases} n, ~ i = n\\ -num_i, ~ i \neq n \end{cases} \]
所以上面的式子可以更簡便的表示為
\[ Ans_k = {\sum_{i = 1}^{n} cnt_i \times {i \choose k}} = \frac{1}{k!}~{\sum_{i = 1}^{n}} ~\frac{cnt_i \times i!}{(i - k)!} \]
? 那么把\(~cnt_i \times i!~\)放一起，\(~\frac{1}{(i - k)!}~\)放一起， 用一個\(~FFT~\)套路把\(~(i - k)~\)倒過來之后就可以卷起來了。

? 但是為了求了這個更簡便的式子會導致\(~cnt_i \times i!~\)可能是負數(shù)，而我的\(~NTT~\)已經(jīng)習慣了這樣寫，look down，因為普通題目中要卷起來的一般都是正的，所以一開始就把這題要卷的東西變成正的也是可以的。

a[j + k] = (x + y) % mod, a[j + k + (i >> 1)] = (x - y + mod) % mod;

? 而我一開始沒有轉(zhuǎn)正，所以這樣寫很不優(yōu)秀，因為一旦\(~y~\)是一個比較小的負數(shù)，那么\(~(x - y + mod)~\)就爆\(~int~\)了，我因為這里調(diào)了一個晚上+一個下午，很難受。

最后提一下這個題的模數(shù)是\(~924844033~\)，所以原根是\(~5~\)而不是熟知的\(~3~\) 。

Code

#include<bits/stdc++.h> #define For(i, j, k) for(int i = j; i <= k; ++i) #define Forr(i, j, k) for(int i = j; i >= k; --i) #define Travel(i, u) for(int i = beg[u], v = to[i]; i; i = nex[i], v = to[i]) using namespace std;inline int read() {int x = 0, p = 1; char c = getchar();for(; !isdigit(c); c = getchar()) if(c == '-') p = -1;for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return x *= p; }inline void File() { #ifndef ONLINE_JUDGEfreopen("AGC005F.in", "r", stdin);freopen("AGC005F.out", "w", stdout); #endif }const int N = 2e5 + 10, maxn = N << 2, mod = 924844033; int a[maxn], b[maxn], e = 1, beg[N], nex[N << 1], to[N << 1]; int rev[maxn], bit, len, siz, invg[maxn], powg[maxn]; int fac[N], inv[N], cnt[N], sz[N], u, v, n;inline int qpow(int a, int b) {int res = 1;for (; b; a = 1ll * a * a % mod, b >>= 1) if (b & 1) res = 1ll * res * a % mod;return res; }inline void Init(int n) {fac[0] = inv[0] = 1;For(i, 1, n) fac[i] = 1ll * i * fac[i - 1] % mod;inv[n] = qpow(fac[n], mod - 2);Forr(i, n - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod; }inline void add(int x, int y) {to[++ e] = y, nex[e] = beg[x], beg[x] = e;to[++ e] = x, nex[e] = beg[y], beg[y] = e; }inline void dfs(int u, int f) {sz[u] = 1;Travel(i, u) if (v != f) dfs(v, u), sz[u] += sz[v];-- cnt[sz[u]], -- cnt[n - sz[u]]; }inline void NTT(int *a, int flag) {For(i, 0, siz - 1) if (rev[i] > i) swap(a[rev[i]], a[i]);for (int i = 2; i <= siz; i <<= 1) {int wn = flag ? powg[i] : invg[i];for (int j = 0; j < siz; j += i) {int w = 1;for (int k = 0; k < (i >> 1); ++ k, w = 1ll * w * wn % mod) {int x = a[j + k], y = 1ll * w * a[j + k + (i >> 1)] % mod;a[j + k] = (x + y) % mod, a[j + k + (i >> 1)] = (x - y) % mod; }}}if (!flag) {int g = qpow(siz, mod - 2);For(i, 0, siz - 1) a[i] = 1ll * g * a[i] % mod;} }int main() {File(), Init(N - 5);n = read();For(i, 2, n) u = read(), v = read(), add(u, v);dfs(1, 0), cnt[n] = n;for (siz = 1; siz <= (n << 1); siz <<= 1) ++ bit;For(i, 0, siz - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));int g = qpow(5, mod - 2);for(int i = 1; i <= siz; i <<= 1) {invg[i] = qpow(g, (mod - 1) / i),powg[i] = qpow(5, (mod - 1) / i);}For(i, 0, n) {a[i] = 1ll * cnt[i] * fac[i] % mod;b[i] = inv[n - i];}NTT(a, 1), NTT(b, 1);For(i, 0, siz) a[i] = 1ll * a[i] * b[i] % mod;NTT(a, 0);For(i, 1, n) {int ans = 1ll * a[n + i] * inv[i] % mod;ans = (ans + mod) % mod;printf("%d\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/LSTete/p/9506171.html

總結(jié)

以上是生活随笔為你收集整理的【AGC005F】Many Easy Problems (NTT)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。