# yukicoder No. 1696 Nonnil

[問題](https://yukicoder.me/problems/no/1696)

## 概要

次の条件をすべて満たす長さ$N$の数列Aの個数を出力せよ。

- 各要素は$[1,K]$の整数。
- 与えられた$M$個の$(L_i,R_i)$それぞれについて、$[L_i,R_i]$に属するAの要素が必ず存在する。

## 制約

- $1\le N\le 10^9$
- $1\le K\le 1500$
- $\bmod=998244353$

## 自分の解法

想定解と同じ計算量だけど、包除を使わず形式的冪級数的な解き方をした。$k$と$K$が紛らわしいかもしれん。

想定解と同様、$[L_i,R_i]$のうち、他の区間を含んでいるようなものは要らないので除いておく。これで残った区間は$O(K)$個になり、始端および終端の値の大小について全順序になる。

いったんすぐに思いつくDPとして、値昇順に走査するもので、

$dp[i][j] =$ (最後に1個以上存在する値が$i$のときに、それまで値が確定した項数が$j$であるvalidなAの個数)

というのを考える。すると遷移は
$$dp[i][j] = \sum_{(k,l),~l<j} dp[k][l]\binom{N-l}{j-l}$$
となる。ただし$k$は、$[k+1,i-1]$がどの区間も含まないようにする$k$でなければならない。これはすぐに求まる。

最終的に$[i+1,K]$に区間が含まれていないような$dp[i][j]$について、その合計を求めると答えが出る。

よくやる変換として、
$$dp'[i][j] = dp[i][j]\cdot (N-j)!$$
とおき、

$$dp'[i][j] = \sum_{(k,l),~l<j} dp'[k][l]/(j-l)!$$

として、初期値を$dp'[0][0]=N!$ (あるいは1のままで最後に$1/N!$をかける)というふうにできる。

$dp'[i][j]$の値を$x^j$の係数だと思って$dp'[i]$を多項式で表すことにすると、

$$dp'[i] = \sum_k dp'[k]\cdot (x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots )$$

$$dp'[i] = \left(\sum_k dp'[k]\right) (e^x-1)$$

となる。初期値を$e^0$として書けたので、$dp'[i]$は、$e^{ax}$ ($a\in \{0,1,\ldots ,K\}$)の線形和として表せる。この線形和の係数を状態としてDPすれば良い。

$dp'$を求めるにあたり、右辺の$dp'$の和での$k$の走る領域はスライドする区間になるため、ここはしゃくとりで求められる。
よって$O(K^2)$で$dp'[*]$が列挙でき、$[i+1,K]$に区間が含まれていないような$dp'[i]$について、その$x^N$の係数の合計を求めると良い。

計算量は想定解と同じ。

(使ってないけど、$0^n, 1^n, 2^n, \ldots ,K^n$を全列挙するやつをつかうと$O(K\log N)$が$O(K\log N/\log K)$には減りそう)

## コード

https://yukicoder.me/submissions/704118