G - Count Sequences Editorial by bayashiko
問題は以下のように言い換えられます。
問題
以下の条件を全て満たす整数列 \(B=(b_1,b_2,\ldots,b_N)\), \(C=(c_1,c_2,\ldots,c_N)\) の組 \((B,C)\) の個数を \(998244353\) で割った余りを求めてください。
- \(b_1\) は \(0,1,2\) のいずれかである
- \(i=2,3,\ldots,N\) について、 \(b_i\) は \(1,2\) のいずれかである
- \(i=1,2,\ldots,N\) について、 \(c_i\) は非負整数である
- \(\displaystyle \sum_{i=1}^{N} b_i + 3\sum_{i=1}^{N} c_i \leq M\)
\(C\) の総和および \(b_1\) の値を固定して考えます。 \(C\) の総和が \(k\) だとすると、そのような \(C\) の個数は全部で \({}_{N-1+k}C_{k}\) 個あります。
このとき、 \(B\) が満たす必要のある条件は以下のようになります。
- \(b_1\) は \(0,1,2\) のいずれかである
- \(i=2,3,\ldots,N\) について、 \(b_i\) は \(1,2\) のいずれかである
- \(\displaystyle \sum_{i=1}^{N} b_i \leq M-3k\)
\(b_1=l\) と固定した上で、更に言い換えを行うと以下のようになります。
- \(i=2,3,\ldots,N\) について、 \(b_i\) は \(0,1\) のいずれかである
- \(\displaystyle \sum_{i=2}^{N} b_i \leq M-3k-l-(N-1)\)
この条件を満たす整数列 \(B'=(b_2,b_3,\ldots,b_N)\) の個数が\(\displaystyle \sum_{i=0}^{M-3k-l-(N-1)} {}_{N-1}C_{i} \) 個であることは明らかです。この値は \({}_{N-1}C_{0},{}_{N-1}C_{1},\ldots,{}_{N-1}C_{N-1}\) の累積和を計算しておけば \(O(1)\) で求めることが出来ます。
以上より、この問題の答えは \(\displaystyle \sum_{i=0}^{\lfloor \frac{M}{3} \rfloor}{}_{N-1+i}C_{i} \sum_{j=0}^{2} \sum_{k=0}^{M-3i-j-(N-1)} {}_{N-1}C_{k}\) です。
posted:
last update: