More Related Content
What's hot (20)
Similar to Aizu-2017: B (20)
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
Aizu-2017: B
- 1. えびちゃんと数列 ? 原案：栗田、鳥谷部 ? 問題文：瀧澤 ? 解答：栗田、杉江、瀧澤 ? 解説：瀧澤 会津合宿2017 Day3 B問題
- 2. 問題概要 ? 以下の個数を mod 109 + 7 で求める – 長さ ? の等差数列 ?? – 各要素 ?? は整数で 0 ≤ ?? ≤ ? を満たす ? 制約 – 1 ≤ ? ≤ 1015 – 0 ≤ ? ≤ 1015 ? 32bit 整数では収まらない
- 3. サンプル1 ? 入力 – 長さ ? = 3 – 上限値 ? = 9 ? 出力 – 50 ? 0, 0, 0 , 0, 1, 2 , … , 2, 1, 0 , 2, 2, 2 , … , 9, 9, 9
- 4. 解説（1/5） ? 数学的なことを考える必要がある – ループなどでの数え上げでは間に合わない ? ?, ? の上限がとても大きいため ? 数列の初項と末項を定めればよい – 等差数列なので、残りは一意に求まる – どう定めよう？
- 5. 解説（2/5） ? 公差の満たす条件を考える – 整数列なので、整数である必要がある（自明） ? このとき初項と末項の差は ? ? 1 の倍数になる ? これにより、数えるべきものを言い換えられる – 以下の条件を満たす非負整数の順序対 ??, ?? ? ?, ? ≤ ? ? ? ? ? が ? ? 1 の倍数である – これは次ページ以降の要領で ? 1 で求まる
- 6. 解説（3/5） ? ? = 6, ? = 11 を例に考える – 0, 5, 10 から順序対を作る→ 32 = 9 – 1, 6, 11 から順序対を作る→ 32 = 9 – 2, 7 , 12 から順序対を作る→ 22 = 4 – 3, 8 , 13 から順序対を作る→ 22 = 4 – 4, 9 , 14 から順序対を作る→ 22 = 4 ∴ 30 mod 5 0 1 2 3 4 0 1 2 3 4 5 6 7 8 9 10 11 mod ? ? 1 で ? 以下の 非負整数を分ける
- 7. 解説（4/5） ? ? = 6, ? = 11 を例に考える ? 総数は ? ? ? + 1 2 + ? ? ? ? 1 ? ?2 – 表の横幅は ? ? 1、要素数は ? + 1 – ? が ? ? 1 の倍数の場合は赤い方が潰れる mod 5 0 1 2 3 4 0 1 2 3 4 5 6 7 8 9 10 11 ? = ? + 1 ? 1 ? ? 1? + 1 ? = ? + 1 ? ? ? 1 ? ? ? ? 1 ? ?
- 8. 解説（5/5） ? オーバーフローには注意 – 64bit 整数でも 1015 同士の掛け算は無理 – うまく工夫する ? 順序を変えたり、先に mod をとったり ? ゼロ除算にも注意 – ? = 1 の場合は分ける ? 総数は自明に ? + 1 ? ここでも mod をとるのを忘れずに
- 9. Writer 解 ? C++ – 栗田：23行 – 杉江：33行 – 瀧澤：30行 ? Python – 栗田：11行 – 杉江：10行