競プロを頑張るブログ

問題を解いてる時の思考なりをまとめていきます

yukicoder1049を解いた

c++ yukicoder 競プロ 競技プログラミング 解法

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.1049 Zero (Exhaust) - yukicoder

星2.5の問題です。 苦手な組み合わせ問題でした＞＜。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。











問題概要

最初、N = 0とします。
次の操作をK回行います。

  1. N = (N + i) % P
  2. N = (N * i) % P

ただし 0 ≦ i < Pの任意整数、Pは素数

最終的にNが0になる操作パターンを数え上げましょう！

考察

可能な操作を全パターン試すDPを初めに考えてみると、現在値nと残り操作回数kを引数に取れば良さそうかな？
nは毎回Pで割られるから、テーブルサイズはO(P * K)で1015になって・・・

多すぎだね。

戻り値も109 + 7で割ってるから大きいね、引数と戻り値の交換もダメそう。

操作2だけに注目した場合は、Nが0になった場合はどんな操作しても値が変わらないね。

Nが0以外の数値だった時の終端操作を考えてみようかな。

操作1(加算)でNを0にするには・・・
P未満の数値に、P未満の数値を足してPの倍数にするには(P - N)を足してあげるしかないね。

操作2(乗算)でNを0にするには・・・
Pが素数だから、P未満の数値からPの倍数を作るには0を乗算するしかないね。

Nがどんな値だろうと最終的に0を作れそうだね。

上記から考えて、操作回数Kが2の場合を考えてみよう。

N=0のまま保つには0加算(1通り)か任意乗算(P通り)のP + 1通りだね。
0以外に移るには加算だけ考えて(P - 1)通りかな。

2回目の操作では、Nを0にしなきゃいけいないから・・・
現在値が0の場合は、0加算と任意乗算でP + 1通り。
現在値が0以外の場合は、いい感じの加算(1通り)と乗算(1通り)を考えて2通りかな。

P = 2で試してみよう。

1回目操作時に0になるのが、2 + 1の3通り。 0以外になるのが、2 - 1で1通り。

2回目操作時は3 * (2 + 1)で9通りと、
1 * 2の2通りを足して11通り！正しそう！

K回の操作を考えるときも、0になる場合と、それ以外になる場合でパターンを保存しながら組み合わせを考えれば良さそうだね。

サンプルも無事考えられて、AC！

あとがき + 解法(ネタバレ全開)











解いてる最中に立てた方針通りでした。

操作後に0になる組み合わせと、それ以外になる組み合わせを数えました。

n回目に0になる組み合わせは、0 → 0の組み合わせと、0以外 → 0の組み合わせを足して求めます。

  • 0 → 0：n - 1回目に0になる組み合わせ * (P + 1)
    (P + 1) ... 任意の乗算(P通り) + 0加算(1通り)

  • 0以外 → 0: n - 1回目に0以外になる組み合わせ * 2
    2 ... (P - n)を加算する場合(1通り) + 0乗算(1通り)

n回目に0以外になる組み合わせは、0 → 0以外の組み合わせと、0以外 → 0以外の組み合わせを足して求めます。

  • 0 → 0以外：n - 1回目に0になる組み合わせ * (P - 1)
    (P - 1) ... (P - n)を加算する場合の補集合(P - 1通り)

  • 0以外 → 0以外：n - 1回目に0以外になる組み合わせ * (P - 1 + P - 1)
    (P - 1 + P - 1) ... (P - n)加算の補集合(P - 1通り) + 0乗算の補集合(P - 1通り)

これをK回考えて、最終的に0になる組み合わせを採用してあげればACです！

随時109 + 7で割るのを忘れないでくださいね。

ソースコード

ll MOD = 1'000'000'000 + 7;
ll mod(ll v) {
  if (v >= MOD) return v % MOD;
  return v % MOD;
}

int main() {
  int input(p, k);

  ll zero_pattern = 1;
  ll other_pattern = 0;
  ll to_zero = 0;
  ll to_other = 0;
  REP(i, k) {
    to_zero = mod(zero_pattern * (p + 1) + other_pattern * 2);
    to_other = mod(zero_pattern * (p - 1)) + mod(other_pattern * (p - 1 + p - 1));

    zero_pattern = to_zero;
    other_pattern = to_other;
  }
  print(zero_pattern);
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

REPと入出力のみ使用しています。
REPは半開区間となっています。

https://yukicoder.me/submissions/493276

0になる組み合わせ、0以外になる組み合わせの計算で、それぞれお互いの1状態前を使っているため即変数に代入すると計算結果がずれます。

zero_patternの初期値が1なのは、軽く計算した結果、1が都合良さそうだったからそうしました。。。
Nが0から始まってるので、直感的には1になりますよねっ！

それでは、またっ！

おまけ

小さいケースの確認には考察の冒頭にある全探索で確認していました。

自分で定義した数式があってるかな？って考えるときに、愚直実装で確認するのはおすすめです！