けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

積の和に関する問題

AtCoder ABC 357 F - Two Sequence Queries (2D, 青色, 550 点)

maspy さんの次のツイートがすべて!! F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…

AtCoder ARC 167 A - Toasts for Breakfast Party (灰色, 300 点)

面白かった! 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…

「積の和」典型の、最も典型的な問題

将来、「積の和」タグを開いたときに、最も典型的な問題が目に入るように。なお、二項係数 を と表記することにする。 問題概要 長さが で総和が であるような、正の整数のみからなる数列 は 通り考えられる。これらすべての数列についての の総和を 9982443…

競プロキャンプ2023関西 L - (sum)mer

FPS + 負の二項係数 問題へのリンク 問題概要 長さが で総和が であるような、正の整数のみからなる数列 すべてについての の総和を 998244353 で割ったあまりを求めよ ( ケース)。 制約 解法 (1):FPS 求めたいものは である。これはちゃんと計算すると、 …

AOJ 3209 Times Square (OUPC 2020 A)

ABC C にありそうな教育的問題! 問題へのリンク editorial 問題概要 正の整数 が与えられる。 かつ を満たすすべての整数組 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 (テストケース数) 考えたこと 結局、 を計算すればよい。それぞれ…

AtCoder ARC 110 D - Binomial Coefficient is Fun (黄色, 600 点)

色んな解法がありそう。 問題へのリンク 問題概要 個の正の整数 が与えられる。 を満たすすべての非負整数列 に対する の総和を 1000000007 で割ったあまりを求めよ。 制約 解法 (1):経路数への帰着 (僕の解法) 二項係数を扱う方法論として、経路数へと帰着…

CodeChef Practice(Easy) GCD Sum

添字 GCD 畳み込みの練習問題! 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

AtCoder ABC 043 C - いっしょ (ARC 059 C) (5Q, 茶色, 200 点)

本当にただ全探索するだけ!!! でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…

yukicoder No.1145 Sums of Powers

形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…

AtCoder ARC 106 D - Powers (青色, 600 点)

「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution (橙色, 800 点)

これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…

AtCoder AGC 001 E - BBQ Hard (1400 点)

当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける!!! というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…