http://tdpc.contest.atcoder.jp/
PQRSは結構難しい(はず)。解いたやつから順番にあげていきます。
P
木dpするだけのO(NK^2)、と言ってしまえばおしまいだが木dpはバグらせがち。
最初点を主役にして、dpの遷移が意味不明になった。
dp[v][K]:=((vのsubtreeに含まれる辺)+(vとvの親を結ぶ辺)がK本のpathを持つとき)と定義すると解きやすい。
木は点と辺どっちを主役にするかが大事ってそれ一番言われているから。
あとdpテーブルを二つ持つやり方よりも実装が楽な方法がありそうだと思った。
int N, K; ll dp[1010][60][2]; ll dp2[1010][60][3]; vector<int> G[MAX_N]; void loop(int v, int p) { int n = (int)G[v].size(); rep(i, 0, n) { int to = G[v][i]; if(p == to) continue; loop(to, v); } dp2[0][0][0] = 1; rep(i, 0, n) { int to = G[v][i]; if(p == to) { rep(j, 0, K + 2) rep(k, 0, 3) dp2[i + 1][j][k] = dp2[i][j][k]; } else { rep(j, 0, K + 2) rep(k, 0, 3) dp2[i + 1][j][k] = 0; rep(j, 0, K + 2) { rep(k, 0, 3) { for(int l = 0; l + j <= K + 1; l++) { ADD(dp2[i + 1][l + j][k], dp2[i][j][k] * dp[to][l][0] % mod); if(k != 2) { ADD(dp2[i + 1][l + j][k + 1], dp2[i][j][k] * dp[to][l][1] % mod); } } } } } } rep(j, 0, K + 2) { if(j != 0) ADD(dp[v][j - 1][0], dp2[n][j][2]); ADD(dp[v][j][0], dp2[n][j][1]); ADD(dp[v][j][0], dp2[n][j][0]); ADD(dp[v][j][1], dp2[n][j][1]); ADD(dp[v][j + 1][1], dp2[n][j][0]); } } void solve() { cin >> N >> K; rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } loop(0, -1); cout << dp[0][K][0] << "\n"; }
Q
R
何も考えずに最小費用流…をすると死ぬ。
sourceから流れず、負のループ内で完結してしまう流れ方が存在してしまうからだ。
最小費用流はsourceから必ず流れてほしいというシチュエーションが多いので、負のループがある時点でほかの解法を考える方がいいかもしれない。今回はSCCしてDAGにしてから最小費用流すれば良い。(最小費用流の方が脳死で楽だが、もちろんDPでもできる)
SCCとMCFをいっぺんに使うとゴツイ感じ(コード長5425Byte)になって好き。
int N; void solve() { cin >> N; SCC::init(N); rep(i, 0, N) { rep(j, 0, N) { int a; cin >> a; if(!a) continue; SCC::add_edge(i, j); } } N = SCC::get(); int s = 2 * N, t = 2 * N + 1; MCF::init(2 * N + 2); rep(i, 0, N) { rep(j, 0, (int)SCC::nG[i].size()) { int v = SCC::nG[i][j]; MCF::add_edge(i + N, v, inf, 0); } } rep(i, 0, N) { MCF::add_edge(i, i + N, 1, -(int)SCC::C[i].size()); MCF::add_edge(i, i + N, inf, 0); MCF::add_edge(s, i, inf, 0); MCF::add_edge(i + N, t, inf, 0); } cout << -MCF::get(s, t, 2) << "\n"; }
S
グラフの接続関係を持ってDPすればいいです。適当に順番つけて状態量を減らしましょう。
int M, N; map<vi, ll> dp[110]; int used[12]; void loop(const vector<vi>& G, int v, int at) { used[v] = at; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(used[n] == M) loop(G, n, at); } } void solve() { cin >> M >> N; vi tv(M, M); tv[0] = 0; dp[0][tv] = 1; rep(i, 0, N) { for(auto& p: dp[i]) { rep(bit, 0, (1 << M)) { fill(used, used + 2 * M, M); vi vec = p.fst; ll v = p.sec; vector<vi> G(2 * M); rep(i, 0, M) { rep(j, i + 1, M) { if(vec[i] == vec[j]) { G[i].pb(j); G[j].pb(i); } } if(vec[i] != M && (bit & (1 << i))) { G[i].pb(i + M); G[i + M].pb(i); } } rep(i, 0, M - 1) { if((bit & (1 << i)) && (bit & (1 << (i + 1)))) { int a = i + M, b = i + M + 1; G[a].pb(b); G[b].pb(a); } } rep(i, 0, M) { if(vec[i] == 0 && used[i] == M) { loop(G, i, 0); } } int at = 1; rep(i, 0, M) { if(used[i + M] == M && (bit & (1 << i))) { loop(G, i + M, at++); } } vi nv = vi(used + M, used + 2 * M); ADD(dp[i + 1][nv], v); } } } ll ans = 0; for(auto& p : dp[N]) { vi vec = p.fst; ll v = p.sec; if(vec[M - 1] == 0) ADD(ans, v); } cout << ans << "\n"; }
T
kitamasa法やるだけ。O(k^2log(N))。F(n)=b(k-1)*F(k-1)+b(k-2)*F(k-2)...+b(0)*F(0)として係数のbを求めていく。
F(n)→F(2*n)を求める際2stepで計算する。
1.F(n)を使ってF(2*n)をF(0)...F(2k-1)で表す。
2.F(K)...F(2k-1)をF(0)...F(k-1)で表す。
1はFFTそのものなのでO(klogk)で求められるが、2はFFTできずどうしてもO(k^2)かかると思うんだけどどうだろう…
vl inc(const vl& vec) { int n = (int)vec.size(); vl res(n, 0); rep(i, 0, n - 1) { res[i + 1] = vec[i]; } rep(i, 0, n) ADD(res[i], vec[n - 1]); return res; } int K, N; vl D[MAX_N]; vl mod_fib(ll n) { if(n < 2 * K) return D[n]; if(n % 2 == 1) return inc(mod_fib(n - 1)); else { vl vec = mod_fib(n / 2); vl tmp(2 * K, 0); rep(i, 0, K) { rep(j, 0, K) { ADD(tmp[i + j], vec[i] * vec[j] % mod);//step1 } } vl res(K, 0); rep(i, 0, 2 * K) { if(i < K) ADD(res[i], tmp[i]); else { rep(j, 0, K) { ADD(res[j], D[i][j] * tmp[i] % mod);//step2 } } } return res; } } void solve() { cin >> K >> N; rep(i, 0, K) { D[i] = vl(K, 0); D[i][i] = 1; } D[K] = vl(K, 1); rep(i, K + 1, 2 * K) D[i] = inc(D[i - 1]); vl fib = mod_fib(N - 1); ll res = 0; rep(i, 0, K) ADD(res, fib[i]); cout << res << "\n"; }
QとSが解ける見込みがないです…
(2/5/2017更新)あとQだけですね。