解けたと思ったけど計算量の見積もりが甘かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14506
https://community.topcoder.com/stat?c=problem_statement&pm=14556
問題
M個の木を成すグラフT(i)がある。
各グラフはN頂点からなり、0~(n-1)のラベルが振られている。
ここで、以下の処理を行う。
- 各グラフで任意の辺を1つずつ選び、取り除く。
- T(i)で取り除いた辺の両端の頂点をu,vとすると、T((i+1)%M)のグラフでu-v間に辺を張る。
処理を行った後も各グラフが木であるような選び方は何通りか。
解法
T(i)でj番目の辺を取り除いたとき、次にT((i+1)%m)で取り除くことができる辺を列挙しよう。
これは全頂点間の距離などを用いれば容易にできる。
あとはT(0)で取り除く辺を総当たりし、以後それぞれT(1)、T(2)…と各辺を取り除く組み合わせを求めていき、最後にまたT(n-1)で取り除く辺に対し、最初にT(0)で選んだ辺を取り除くことができる場合の数を求めればよい。
この解法を愚直に書くとO(M*N^3)であり、Div2は通るがDiv1はTLEする。(自分もこれで落ちた)
これをもう少し高速化することを考える。
最初の「T(i)でj番目の辺を取り除いたとき、次にT((i+1)%m)で取り除くことができる辺を列挙しよう。」をもう少し賢くやろう。
T(i)でu-v間の辺を取り除くとき、T((i+1)%m)で取り除く辺の条件を考える。
T((i+1)%m)には最初u-v間の辺を追加するので、次に辺を取り除いた後T((i+1)%m)が木であるためには、もともとu-v間にあった辺のいずれかを切ればよい。
言い換えると、u-LCA(u,v)-v間の辺が切る対称となる。
先に前処理でLCA(u,v)を求めておくと、あとはimos法の要領で処理を高速化できる。
ll mo=1000000007; vector<pair<int,int>> E[303][303]; vector<pair<int,int>> E2[303]; int par[303][303]; int pv[303][303]; int D[303][303]; int lca[303][303]; vector<int> O[303]; int dp[303][303]; class TreeMoving { public: int add(int& a,int b) { a += b; if(a>=mo) a-=mo; return a; } void dfs(int id,int cur,int pre,int d) { D[id][cur]=d; FORR(e,E[id][cur]) { if(e.first==pre) { par[id][cur]=pre; pv[id][cur]=e.second; } else { dfs(id,e.first,cur,d+1); } } O[id].push_back(cur); } int count(int n, vector <int> roots, vector <int> a, vector <int> b, vector <int> c) { int i,k,j,x; int m=a.size(); FOR(i,303) FOR(k,303) E[i][k].clear(); FOR(i,m) { E2[i].clear(); ll X=c[i]; FOR(j,n-1) { int u=(roots[i]+j+1)%n; int v=(roots[i]+(X%(j+1)))%n; E[i][u].push_back({v,j}); E[i][v].push_back({u,j}); E2[i].push_back({u,v}); X = (a[i]*X+b[i])%mo; } O[i].clear(); dfs(i,0,-1,0); } FOR(i,m) { FOR(k,n-1) { int u=E2[i][k].first; int v=E2[i][k].second; j = (i+1)%m; while(D[j][u]<D[j][v]) v=par[j][v]; while(D[j][u]>D[j][v]) u=par[j][u]; while(u!=v) v=par[j][v], u=par[j][u]; lca[i][k]=u; } } ll ret=0; FOR(x,n-1) { ZERO(dp); dp[0][x]=1; FOR(i,m) { int sum[303]={}; FOR(k,n-1) { add(sum[E2[i][k].first],dp[i][k]); add(sum[E2[i][k].second],dp[i][k]); add(sum[lca[i][k]],mo-dp[i][k]); add(sum[lca[i][k]],mo-dp[i][k]); } FORR(o,O[(i+1)%m]) if(o) { add(dp[i+1][pv[(i+1)%m][o]],sum[o]); add(sum[par[(i+1)%m][o]],sum[o]); } } ret += dp[m][x]; } return ret%mo; } }
まとめ
一応いくつかのケースでTLEしないこと確認して出したのだけど、ダメだったね。