2020-06-23

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 までを足す」分の計算量でいい.
f:id:tac_12:20200623234317p:plain:w300

ソースコード
 https://atcoder.jp/contests/abc171/submissions/14641134

類題
https://tac-12.hatenablog.com/entry/2020/05/11/154759

2020-06-16

Matrix Game - #648 div2 a

問題

n * m の, 0, 1 のマスが与えられる.
2 人でゲームをする.
各ターン, あるマスの行, 列で, 1 のマスがないマスを 1 にできる (隣とは限らないよ).
相手が 1 にできなくなったら勝ち.

解法

1 のマスがない行, 列の個数をそれぞれ数える.
それらの小さい方回操作ができる.
偶奇で判定.

ソースコード
 https://codeforces.com/contest/1365/submission/83931135

2020-06-07

ModSum - abc 139 d

問題

$x_1, ..., x_n$ を 1, ..., n の permutation として,
$x_1 \ mod \ 1 + x_2 \ mod \ 2 + ... + x_n \ mod \ n$ を最大化する.

解法

$x_1, ..., x_n$ で, mod をとってできるだけ小さくならないようにする, と考えない.

mod をとる側で, できるだけ大きくしようとする.
mod 1 で最大は 0.
mod 2 で最大は 1.
のように.

$x_2 = 1, x_3 = 2, ..., x_n = n - 1, x_1 = n$ とすれば最大値が達成できる.

問題
D - ModSum

2020-06-06

Johnny and Contribution - #647 div2 d

問題

木と, 各頂点で得るべき数が与えられる.
各頂点で得る数は, 隣り合う頂点で, すでに数を得た頂点の数にない数の最小値.
どの順番で頂点が数を得るか求める.

解法

各頂点, 得るべき数と得る数を一致させる.

得るべき頂点.
数 x を得るべき頂点において, 得るべき数が 1, 2, ..., x-1 の頂点すべてを隣り合う頂点に持つ必要がある.

得るべき数が小さい数から見る.
隣り合う頂点で, 数 1, 2, ..., x-1 が 1 回ずつ count されていればいい.

ソースコード
 https://codeforces.com/contest/1362/submission/82704121

2020-05-28

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) + $1 - (x - i)^{p - 1}$ .

x = i のとき, x - i = 0 で, f'(x) = f(x) + 1.

x $\neq$ i のとき, $(x - i)^{p - 1} \equiv 1$ (mod p) で, f'(x) = f(x).

x - i と素数 p が互いに素であることを示す.
$0 \leq i, x \leq p - 1$ .
ただし, x $\neq$ i.

-(p - 1) $\leq$ x - i $\leq$ p - 1.
ここで, x $\neq$ 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

参考
https://www.youtube.com/watch?v=1Z6ofKN03_Y