https://yukicoder.me/problems/no/980 前提知識 母関数 解説 https://yukicoder.me/submissions/424776 問題を見ると数列を作成して、畳込み計算をすれば答えられる。 今回は、各所で解説されている母関数で解く方法を解説しよう。 まず、元々の数列は線形…

https://yukicoder.me/problems/no/979 前提知識 LIS 解説 https://yukicoder.me/submissions/424709 LISに問題設定が似ているので、LISに寄せた感じで考えてみる。 DPっぽくやっていく。 dp[i][x] := i番目まで考え終わっていて、末尾の値がxである最長列の…

https://yukicoder.me/problems/no/978 解説 https://yukicoder.me/submissions/424701 数列自体は作成できるので、作成してしまおう。 答えを見てみると畳み込み計算をして総和みたいな感じになっている。 だが、畳み込み計算するには、制約が厳しいし、★も…

https://yukicoder.me/problems/no/977 前提知識 UnionFind 二重辺連結成分分解 解説 https://yukicoder.me/submissions/424691 Aliceは連結成分を最大1つ増やすことができるし、Bobは連結成分を最大1つ減らすことができる。 Bobが連結成分をへらすことがで…

https://yukicoder.me/problems/no/976 解説 https://yukicoder.me/submissions/424685 mod m上の計算では、ab % m = (a % m) * (b % m)が成り立つ。 つまり、分配法則が成り立つため、Mで割ったあまりを計算しながら、2を128回かけていけばいい。 ll M; //-…

https://yukicoder.me/problems/no/975 解説 https://yukicoder.me/submissions/424682 あるかどうかをそれぞれ判定して、booleanの変数として保持しておこう。 あとは、それを使って、4択の回答方法で答える。 int X, N, M, A[101010], B[101010]; //------…