Strivore - abc 171 f
#二項係数
まず, 愚直な dp を考える.
rep(i, sz) rep(j, sz(s) + 1) rep(l, 26) { if (s[j] - 'a' == l) add(dp[i + 1][j + 1], dp[i][j]); else add(dp[i + 1][j], dp[i][j]); } cout << dp[sz][sz(s)] << endl;
rep(l, 26) をなくすと以下のようになる.
rep(i, sz) rep(j, sz + 1) { add(dp[i + 1][j + 1], dp[i][j]); add(dp[i + 1][j], 25LL * dp[i][j] % mod); } ll ans = 0; rep3(i, sz(s), sz + 1) add(ans, dp[sz][i]); cout << ans << endl;
sample 1 で dp の違いを確かめる.
1 0 0 0 0 25 1 0 0 0 625 50 1 0 0 15625 1875 75 1 0 390625 62500 3750 101 0 9765625 1953125 156250 6376 0 244140625 58593750 5859375 322026 0 103515583 708984368 205078125 14232051 0 587889561 828124664 835937458 575111451 0
1 0 0 0 0 0 0 0 0 0 25 1 0 0 0 0 0 0 0 0 625 50 1 0 0 0 0 0 0 0 15625 1875 75 1 0 0 0 0 0 0 390625 62500 3750 100 1 0 0 0 0 0 9765625 1953125 156250 6250 125 1 0 0 0 0 244140625 58593750 5859375 312500 9375 150 1 0 0 0 103515583 708984368 205078125 13671875 546875 13125 175 1 0 0 587889561 828124664 835937458 546875000 27343750 875000 17500 200 1 0
5 行目で, 100 1 か 101 か違いが出始める.
下のコードでは, すべて *1 の遷移と *25 の遷移があるのに対し, 上のコードでは, j = sz(s) のとき, *26 の遷移をする.
よって, 下のコードでは, dp[sz] の sz(s) ~ sz までを足す.
手書きで遷移を書いてみると, 二項係数が見えてくる.
よって, dp[sz] の「sz(s) ~ sz までを足す」分の計算量でいい.
ソースコード
https://atcoder.jp/contests/abc171/submissions/14641134
Matrix Game - #648 div2 a
問題
n * m の, 0, 1 のマスが与えられる.
2 人でゲームをする.
各ターン, あるマスの行, 列で, 1 のマスがないマスを 1 にできる (隣とは限らないよ).
相手が 1 にできなくなったら勝ち.
解法
1 のマスがない行, 列の個数をそれぞれ数える.
それらの小さい方回操作ができる.
偶奇で判定.
ソースコード
https://codeforces.com/contest/1365/submission/83931135
ModSum - abc 139 d
問題
を 1, ..., n の permutation として,
を最大化する.
解法
で, mod をとってできるだけ小さくならないようにする, と考えない.
mod をとる側で, できるだけ大きくしようとする.
mod 1 で最大は 0.
mod 2 で最大は 1.
のように.
とすれば最大値が達成できる.
問題
D - ModSum
Johnny and Contribution - #647 div2 d
問題
木と, 各頂点で得るべき数が与えられる.
各頂点で得る数は, 隣り合う頂点で, すでに数を得た頂点の数にない数の最小値.
どの順番で頂点が数を得るか求める.
解法
各頂点, 得るべき数と得る数を一致させる.
得るべき頂点.
数 x を得るべき頂点において, 得るべき数が 1, 2, ..., x-1 の頂点すべてを隣り合う頂点に持つ必要がある.
得るべき数が小さい数から見る.
隣り合う頂点で, 数 1, 2, ..., x-1 が 1 回ずつ count されていればいい.
ソースコード
https://codeforces.com/contest/1362/submission/82704121
Polynomial Construction - abc 137 f
#math
ヒント
すべて 0 の数列から, 1 ずつ足して 0, 1 の数列 a を構成する.
解法
a = 0 ... 0
から
a' = 0 0 ... 0 1 0 ... 0
と, i 番目のみ 1 にすることを考える.
a に対応する f(x) から, a' に対応する f'(x) を構成する.
f'(x) = f(x) + .
x = i のとき, x - i = 0 で, f'(x) = f(x) + 1.
x i のとき, (mod p) で, f'(x) = f(x).
x - i と素数 p が互いに素であることを示す.
.
ただし, x i.
-(p - 1) x - i p - 1.
ここで, x i より, x - i は p の倍数にならない.
以上より, 与えられる a に対して f(x) が求まったので, 各 x の冪乗の係数を求める.
tle 3000 * 3000 * 11 > 10^8
vector<int> b(p); rep(i, p) { if (a[i] == 0) continue; b[0]++; // (x-i)^(p-1) = (p-1)Cj x^j (-i)^(p-1-j) rep(j, p) { (b[j] += mod - COM(p - 1, j) * modpow(-i, p - 1 - j, mod) % mod) %= mod; } }
modpow のところを O(1) で計算できる.
j を後ろから走査して, -i をかけていく.
ソースコード
tle
https://atcoder.jp/contests/abc137/submissions/13663541
ac
https://atcoder.jp/contests/abc137/submissions/13663696
Orac and Game of Life - #641 div2 e
問題
n * m の 0 か 1 の grid が与えられる.
毎ターン, それぞれのマスが, 隣り合う同じ色のマスをもたなければそのままで, それ以外なら 0, 1 反転する.
t つの query が与えられる.
p ターン後, マス (i, j) の数を答える.
考察
市松模様なら, 最初の grid のまま.
隣あう同じ数のマスがあれば, ともに反転する.
隣に同じ数のマスができたら, 以降反転し続ける.
0101010
1010101
0101010
1010100
のように, 市松模様で部分的に壊れている場合, そこから反転するマスが広がっていく.
最初の grid で, 一番近い, 反転するマスがわかればいい.
計算量が...
解法
「最初の grid で, 一番近い, 反転するマスがわかればいい」と上に書いたが, bfs でやる.
ソースコード
https://codeforces.com/contest/1350/submission/81448139
Orac and Medians - #641 div2 d
#中央値
本番
k より小さい数を -1, k を 0, k より大きい数を 1 にする.
ランレングス圧縮する.
0 と隣り合う 1 は 0 にできる.
なぜなら, k と k より大きい数 2 つの区間を選べば, 順々に k にできるから.
1 -1 0 -1 0 -1 0 -1 ...
のようになる.
ランレングス圧縮しているので, 連続した -1 を 1 つの -1 で表している.
個数の情報も持っている.
前から 0 -1 0 を見て, 0 の個数が -1 の個数より大きかったら 0 0 0 にするというのが考えられる.
計算量が心配.
0 -1 0 -1 0 -1 0 ... 0 -1 0
1 2 1 2 1 2 1 ... 1 2 100 : 個数
のような場合.
解法
上のように, 端の 1 以外の 1 を 0 にした後, 端の 1 と すべての 0, 2 つで, 隣り合うものか 1 つとばしのものがあれば, すべてを 0 にできる.
k 2 つと k 未満 1 つ, もしくは k 1 つと k より大きい数 1 つと k 未満の数 1 つの 3 つの区間を選べば, 3 つとも k になる.
また, 距離 2 以下の k 以上の数が存在しなければ不可能.
k = 3 で, 3 2 2 4 では どの区間をとっても 2 に変わる.
3 2 2 4 の外側に延ばしても, k 未満の数が, k 以上の数の個数以上加わるので, すべてを k にするのは不可能.
ソースコード
https://codeforces.com/contest/1350/submission/81442945