首页 > 其他分享 >CF1093F

CF1093F

时间:2022-11-01 16:12:24浏览次数:37  
标签:tmp CF1093F int d% len mx mod

设 \(f_{i,j}\) 表示前 \(i\) 个位置,第 \(i\) 个位置的数字是 \(j\) 的方案数,\(s_i=\sum_{j}f_{i,j}\),\(mx_{i,j}\) 为位置 \(i\) 往前全是 \(j\) 的最长长度。

\(f_{i,j}=\left\{\begin{matrix} s_{i-1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ mx_{i,j}\lt len \\ s_{i-1}-(s_{i-len}-f_{i-len,j}) \ \ \ \ \ mx_{i,j}\ge len \end{matrix}\right.\)

上面显然,因为随便选一定合法。

而 \(s_{i-1}-(s_{i-len}-f_{i-len,j})\) 的意义是,之前的随便选的方案数 \(s_{i-1}\),减去这个位置恰好出现了 \(len\) 个连续的方案数 \(s_{i-len}-f_{i-len,j}\),由于新加一个数只可能出现恰好 \(len\) 个的非法情况,所以这么减刚好就是真实的答案。

时间复杂度 \(\mathcal O(nk)\)。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 105, mod = 998244353;
int n, k, len;
int a[N], f[N][M], s[N], mx[N][M];

int main() {
	scanf("%d%d%d", &n, &k, &len);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= k; ++j)
			if (a[i] == j || a[i] == -1) mx[i][j] = mx[i - 1][j] + 1;
	s[0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= k; ++j) {
			if (a[i] == j || a[i] == -1) {
				f[i][j] = s[i - 1];
				if (mx[i][j] >= len) {
					int tmp = (s[i - len] - f[i - len][j] + mod) % mod;
					f[i][j] = (f[i][j] - tmp + mod) % mod;
				}
				s[i] = (s[i] + f[i][j]) % mod;
			}
		}
	printf("%d", s[n]);
	return 0;
}

标签:tmp,CF1093F,int,d%,len,mx,mod
From: https://www.cnblogs.com/Kobe303/p/16848051.html

相关文章