20260831 每日 2.0 2.5 4.0

No.741 AscNumber 不下降数字 2.0$

https://yukicoder.me/problems/no/741

比较显然的一个数位 DP，两星还挺合适的

定义 $dp[i][j] :=$ 长度为 $i$ 且最后一位是 $j$ 的不下降数字方案数

转移方程显然是 $dp[i][j] = \sum_{k \le j} dp[i - 1][k]$

初始值就是 $i \in[0, 9],$ $dp[1][i] = 1$

统计结果就是 $\sum_{i = 0}^9 dp[N][i]$

可以使用滚动数组优化，空间复杂度是常数，时间复杂度是 $O(10N)$

//no-unlocked
ll f[1d6 + 2][10];
{
	ll @N;
	rep(i, 10) f[1][i] = 1;
	rep(i, 1, N + 1) {
		rep(j, 10) rep(k, j + 1) (f[i + 1][j] += f[i][k]) %= MD;
	}
	ll ans = 0;
	rep(i, 10) (ans += f[N][i]) %= MD;
	wt(ans);
}

No.3159 Just Answer 10 Integers! 2.5$

https://yukicoder.me/problems/no/3159

有点妙的构造，换句话说就是让最小公倍数都相同，显然会往 $m=1$ 构造对吧。

想一想其实可以想到，如果我们构造一个数 $Prod = 2 \times3 \times 5\times 7$，然后每一个 $S_i = \frac{Prod}{p_i}$

但是这样的话 $S_i$ 会因为过于大而死在 $N = 10$，稍微想一下，实际上只需要 $S_i = \frac{Prod}{p_i - 1}$ 就可以了

//no-unlocked
const int p[] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23};
int @N;
ll S = 1;
rep(i, N) S *= p[i];
VLL ans;
rep(i, N) ans.push_back(S / p[i]);
wt(ans);

No.1696 Nonnil 4.0$

https://yukicoder.me/problems/no/1696

如果我们把 $A$ 内的数字映射到一个集合 $S = \set{x : \exist x \in A}$，那么也就是要有 $S \cap [L_i, R_i] \neq \emptyset$

如果我们定义 $H_s := |\set{S:|S| = s, S 与所有区间都有交集}|$，也就是从 $[1,K]$ 中恰好选择 $s$ 个点，使得每个区间都至少有一个选点。

那么对于一个合法集合 $S$ ，且 $|S| = s$，我们就还要计算：
$$
F(N, s)= |\set{长度为 N 的序列，其映射集合刚好是 S}|
$$
答案其实就是 :
$$
Ans = \sum_{s = 1}^{min(N, K)} H_s \cdot F(N,s)
$$
那么我们第一步先求 $H_s$：

假设选中的数字从小到大是：$x_1 \lt x_2 \lt x_3 \lt \ldots \lt x_s$

我们在两端添加两个点 $x_0 = 0, x_{s+1}=K + 1$

那么一个集合 $S$ 合法，当且仅当：任意相邻两个选点之间，都没有一个完整区间 $[L_i,R_i]$

对于一对相邻点 $p \lt x$，如果其不合法，就有 $p \lt L_i \le R_i \lt x$，我们要没有这样的区间，也就是找到有 $p \ge L_i$ 对于所有满足 $R_i \lt x$ 的区间成立，也就是：$p \ge max_{R_i \lt x} L_i$

所以我们对于每一个选点 $x \in [1, K]$ 构造 $g[x]:= max_{R_i \le x}L_i$

如何构造呢？上式子把去等去掉就有 $max_{R_i \lt x} L_i = g[x - 1]$，因为刚好取不到，于是对于一对相邻选点 $(p, x)$，有 $g[x - 1] \le p \lt x$

于是 $g[x] = max(max_{R_i=x}L_i, g[x - 1])$，两次预处理即可，复杂度 $O(M + K)$

定义 $dp[t][x]:=$ 已经选了 $t$ 个真实数字，且最后一个选的是 $x$ 的方案数

$dp[0][0] = 1$ 初始化虚拟的点。

因为有刚刚的选点约束，所以转移方程是：
$$
dp[t][x] = \sum_{p=g[x - 1]}^{x-1} dp[t - 1][p]
$$
直接求这个式子显然是 $O(K^3)$ 的，枚举 $t, x, p$

但是我们观察到 $g[x - 1]$ 的值域和 $x$ 本身相同，于是可以前缀和优化这个求和

先求 $pre[x] = \sum_{i=1}^x dp[t - 1][i]$，之后这个式子就可以变成：
$$
dp[t][x] = pre[x - 1] - pre[g[x - 1] - 1]

$$
这样就是 $O(K^2)$ 的了

最后 $H_s = \sum_{p = g[K]}^K dp[s][p]$ 就可以了

之后怎么求 $F(N, s)$ 呢？

这里引入第二类斯特林数的定义：$\set{N, s} :=$ 把 $N$ 个元素划分进 $s$ 个互不区分的组内的方案数

而 $F(N, s)$ 实际上就是 $\set{N, s}$ 加上编号，于是有
$$
F(N,s) = s! \cdot \set{N, s} = \sum_{j=0}^s (-1)^{s-j} \binom{s}{j} j^N
$$
这个东西可以直接用右边的公式求，于是我们就可以求出答案了
$$
Ans = \sum_{s=1}^{min(N, K)} H_s \sum_{j=0}^s(-1)^{s-j}\binom{s}{j}j^N
$$
复杂度是 $O(M + K^2 + K \log N)$

//no-unlocked 
#define MD 998244353
using mm = Mint;

ll @N; int @K, @m;

VI bst(K + 1, -1); // bst[r] := \max_{R_i = r} L_i
VI g(K + 1, -1); // g[r] := \max_{R_i <= r} L_i

rep(m) {
	int @L, @R;
	bst[R] >?= L;
}

rep(i, 1, K + 1) g[i] = max(bst[i], g[i - 1]); // bst[i] 前缀最大刚好是 g[i]

vector<vector<mm>> f(K + 1, vector<mm>(K + 1, 0)), pre(K + 1, vector<mm>(K + 1, 0));
f[0][0] = 1;

pre[0][0] = 1;
rep(i, 1, K + 1) pre[0][i] = pre[0][i - 1] + f[0][i];

rep(s, 1, K + 1) {
	rep(x, 1, K + 1) {
		f[s][x] = pre[s - 1][x - 1];
		if(g[x - 1] > 0) f[s][x] -= pre[s - 1][g[x - 1] - 1];
	}
	rep(x, 1, K + 1) pre[s][x] = pre[s][x - 1] + f[s][x];
}

vector<mm> H(K + 1, 0);
rep(s, 1, K + 1) rep(x, g[K], K + 1) H[s] += f[s][x];

vector<mm> F(K + 1, 0); // F(N, s) = s! * {N, s}

Comb<mm> comb;

rep(s, 1, K + 1) {

	rep(j, s + 1) {
		mm tt = 1;
		tt *= (-1) ** (s - j);
		tt *= comb.C(s, j);
		tt *= powmod(j, N, MD);
		F[s] += tt;
	}

}

mm ans = 0;
rep(s, K + 1) ans += H[s] * F[s];
wt(ans);