題目鏈接

https://codeforces.com/contest/997/problem/D

題解

點(diǎn)分治這個(gè)思路想不到==

首先這兩棵樹的笛卡爾積并沒有什么用處，因?yàn)榈芽柗e中的環(huán)就是兩棵樹中各找一個(gè)環(huán)按任意順序歸并起來（且不難證明不同的歸并順序?qū)?yīng)不同的方案）。只需要對(duì)兩棵樹分別求出 \(ans_i\) 表示有多少個(gè)長(zhǎng)度為 \(i\) 的環(huán)。

注意由于 1213 這種環(huán)的存在，我們不能直接欽定某個(gè)具有特殊性質(zhì)的點(diǎn)為起點(diǎn)而忽略起點(diǎn)然后乘以環(huán)長(zhǎng)再去掉周期更小的。一個(gè) naive 的想法是設(shè) \(dp[u_1][u_2][k]\) 表示起點(diǎn)為 \(u_1\) 當(dāng)前在 \(u_2\) 長(zhǎng)度為 \(k\) 的方案數(shù)。考慮點(diǎn)分治，設(shè)分治中心為 \(cent\)，計(jì)算經(jīng)過 \(cent\) 的環(huán)的個(gè)數(shù)。這個(gè)很容易（很套路），設(shè) \(f[u][k]\) 表示 \(u\) 點(diǎn)走了 \(k\) 步到 \(cent\) 且之前沒到過 \(cent\) 的方案數(shù)，\(g[u][k]\) 表示 \(cent\) 走了 \(k\) 步到 \(u\) 的方案數(shù)，轉(zhuǎn)移顯然，求答案枚舉第一次到 \(cent\) 的時(shí)間即可。

時(shí)間復(fù)雜度 \(O(k^2n\log n)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define iter iterator #define riter reversed_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 4000; const int mxM = 75; const int P = 998244353;llong comb[mxN+3][mxN+3]; int m;void updsum(llong &x,llong y) {x = x+y>=P?x+y-P:x+y;}void initcomb(int n) {comb[0][0] = 1ll;for(int i=1; i<=n; i++) {comb[i][0] = comb[i][i] = 1ll; for(int j=1; j<i; j++) updsum(comb[i][j]=comb[i-1][j-1],comb[i-1][j]);} }struct Tree {struct Edge{int v,nxt;} e[(mxN<<1)+3];int fe[mxN+3];int fa[mxN+3];int sz[mxN+3],mxsz[mxN+3]; bool vis[mxN+3];llong f[mxM+3][mxN+3],g[mxM+3][mxN+3];llong ans[mxN+3];vector<int> now;int n,en,cent,siz;void addedge(int u,int v){en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en;}void getCentroid(int u,int prv){now.push_back(u);sz[u] = 1,mxsz[u] = 0;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==prv||vis[v]) continue;getCentroid(v,u);sz[u] += sz[v];mxsz[u] = max(mxsz[u],sz[v]);}mxsz[u] = max(mxsz[u],siz-sz[u]);if(cent==0||mxsz[u]<mxsz[cent]) {cent = u;}}void findCentroid(int u){now.clear(); cent = 0; getCentroid(u,0);}void dfs1(){ // printf("dfs1 %d\n",cent); // printf("now: "); for(int i=0; i<now.size(); i++) printf("%d ",now[i]); puts("");int tsiz = siz;f[0][cent] = 1ll,g[0][cent] = 1ll;for(int i=0; i<m; i++){for(int j=0; j<now.size(); j++){int u = now[j];for(int o=fe[u]; o; o=e[o].nxt){int v = e[o].v; if(vis[v]) continue;if(v!=cent) {updsum(f[i+1][v],f[i][u]);}updsum(g[i+1][v],g[i][u]);}}}for(int i=0; i<now.size(); i++){int u = now[i];for(int j=0; j<=m; j++){for(int k=0; k<=j; k++){updsum(ans[j],f[k][u]*g[j-k][u]%P);}}}for(int i=0; i<now.size(); i++) for(int j=0; j<=m; j++) {f[j][now[i]] = g[j][now[i]] = 0ll;}vis[cent] = true;for(int i=fe[cent]; i; i=e[i].nxt){int v = e[i].v; if(vis[v]) continue;siz = sz[v]>sz[cent]?tsiz-sz[cent]:sz[v]; findCentroid(v);dfs1();}}void solve(){for(int i=1; i<n; i++) {int u = read(),v = read(); addedge(u,v),addedge(v,u);}siz = n; findCentroid(1); dfs1(); // printf("ans: "); for(int i=0; i<=m; i++) printf("%I64d ",ans[i]); puts("");} } T1,T2;int main() {T1.n = read(); T2.n = read(); m = read();initcomb(m);T1.solve();T2.solve();llong ans = 0ll;for(int i=0; i<=m; i++){updsum(ans,comb[m][i]*T1.ans[i]%P*T2.ans[m-i]%P);}printf("%I64d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 997D Cycles in Product (点分治、DP计数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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