题解：CF2041H Sheet Music
xiezheyuan
·
·
题解
简要题意
定义两个长度为 n 的序列 a,b 是相似的，当且仅当对于任意的 1\leq i\lt n，有 \mathrm{sgn}(a_i-a_{i-1})=\mathrm{sgn}(b_i-b_{i-1})。
你需要计算有多少个所有值域为 [1,k]\cap \mathbb{Z} 的长度为 n 的序列，特别地，相似的两个序列仅计算一次。答案对 998,244,353 取模。
## 思路
对于一个序列 $a$，我们用一种特殊的方法来记录这个序列（下文称之为符号序列）：对于每一个 $1\leq i\lt n$，如果 $a_i<a_{i+1}$，就写下 $+$，如果 $a_i>a_{i+1}$，就写下 $-$，否则写下 $=$。可以发现两个序列相似的充要条件是符号序列相同，于是现在我们要对所有合法的长度为 $n-1$ 的符号序列计数。
先考虑只有 $<,>$ 两种符号的符号序列的合法条件，可以去写一个 [最平凡的暴力](https://www.luogu.com/paste/apt1vz4n) 去打个表，观察怎样的符号序列是不合法的（因为合法的貌似很多不方便观察共性）。
可以发现**一个符号序列不合法的充要条件是连续出现了不少于 $k$ 个相同的符号（$+$ 或 $-$）。**
证明也是不难的，必要性证明是平凡的，考虑充分性，不妨改为证明一个连续出现少于 $k$ 个相同符号的符号序列一定是合法的（逆否命题）。假如第一个符号是 $+$，就取初值为 $1$，否则取 $k$。然后每个连续段结束时将其值设定为 $k$ 或 $1$，中间随意设定，容易发现用这个方法可以构造一组合法的对应的原序列。
于是可以设计一个 dp，设 $f(i)$ 表示长度为 $i$ 的合法的符号序列的数量，不难得到：
$$
f(i)=\sum_{j=0}^{i-1}[i-j<k] f(j)
$$
初始值 $f(1)=2$ 或 $f(0)=2$ 表示第一个符号可以填 $<$ 或 $>$。这玩意可以用前缀和简单地优化到 $O(n)$。
最后考虑加上 $=$，由于 $=$ 的性质，我们往一个符号序列中的任意一个位置插入或删除一个 $=$ 都不会改变这个序列的合法性。
于是可以枚举填多少个 $<$ 和 $>$，其余位置全部填 $=$，组合数简单计算一下即可：
$$
\sum_{i=1}^{n-1} \binom{n-1}{i}f(i)
$$
时间复杂度 $O(n)$。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }
int n, k, fact[N], inv[N], f[N], g[N], ans = 1;
int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> k; n--;
fact[0] = fact[1] = inv[0] = inv[1] = 1;
for(int i=2;i<=n;i++){
fact[i] = Mul(fact[i - 1], i);
inv[i] = Mul(inv[mod % i], mod - mod / i);
}
for(int i=2;i<=n;i++) inv[i] = Mul(inv[i], inv[i - 1]);
f[0] = g[0] = 2;
for(int i=1;i<=n;i++){
f[i] = Sub(g[i - 1], (i - k) >= 0 ? g[i - k] : 0);
g[i] = Add(g[i - 1], f[i]);
ans = Add(ans, Mul(binom(n, i), f[i]));
}
cout << ans << '\n';
return 0;
}
// Written by xiezheyuan
```