概要 長さNの整数列Sと長さTの整数列Mが与えられる。Sの部分列とTの部分列のなかで共通するものはいくつあるか。(mod 10^9+7 して出力) 制約 1 ≦ N, M ≦ 2 * 10^3 方針 DP。S = {1, 3, 2}, T = {1, 2, 3, 3, 2, 3}のケースを考える。このとき該当する部分列…

Problem - D - Codeforces 概要 n項の数列aと整数kが与えられる。aをk個の連続する部分列に分解し、f(i)：i番目の項が属する部分列の番号とする。Σai * f(i)の最大値を答えよ。 制約 1 ≦ k ≦ n ≦ 3 * 10 ^ 5 |ai| ≦ 10^6 方針 数列の後ろからの累積和s(k) = …

E - Enumerate Xor Sum 概要 長さNの数列Aが与えられる。i=1, …, Nについて(A1 xor X) + (A2 xor X) + … (Ai xor X)を出力せよ。ただし、X = A1 xor A2 xor … xor Aiとする。 制約 1 ≦ N ≦ 3 * 10^5 0 ≦ Ai 方針 2進けたごとにみていくとうまくいく。各2進け…

C - GCD on Blackboard 概要 N項の数列Aが与えられる。この数列のうち1項を好きな数字に変えて数列全体のGCDを計算する（数字を変えなくてもよい。）。GCDの最大値を求めよ。 制約 1 ≦ N ≦ 2*10^5 1 ≦ A[i] ≦ 10^9 全体の方針 数字を変更する項を固定する。 …