526互联

AtCoder Beginner Contest 258 Ex Odd Steps

发布时间 2023-05-30 22:16:08作者: zltzlt

洛谷传送门

AtCoder 传送门

不错的矩阵快速幂优化 dp 练习题。

考虑一个朴素 dp，\(f_i\) 为组成和为 \(i\) 且用到的数都是奇数的方案数。有转移：

\[f_i = \begin{cases} \sum\limits_{j=0}^{i-1} [i \bmod 2 \ne j \bmod 2] f_j & i \notin A \\ 0 & i \in A \end{cases} \]

考虑前缀和优化，设 \(g_{i, j} = \sum\limits_{i=0}^i [i \bmod 2 = j] f_i\)，那么：

\[f_i = \begin{cases} g_{i, 1 - i \bmod 2} & i \notin A \\ 0 & i \in A \end{cases} \]

\[g_{i, i \bmod 2} = g_{i - 1, i \bmod 2} + f_i = g_{i - 1, i \bmod 2} + [i \notin A] g_{i - 1, 1 - i \bmod 2} \]

\[g_{i, 1 - i \bmod 2} = g_{i - 1, 1 - i \bmod 2} \]

至此得到了一个 \(O(S)\) 的做法。

发现 \([0, S]\) 被 \(A_i\) 分成若干段，并且每一段的转移方程重复。为了方便把 \(i \bmod 2 = 1, i \bmod 2 = 0\) 的相邻两个 \(i\) 放一起考虑，那么相当于 \(g'_0 = 2g_0 + g_1, g'_1 = g_0 + g_1\)。容易刻画成矩阵形式，然后分段转移。注意处理一些端点奇偶性不相同的情况。

时间复杂度 \(O(n \log S)\)。

code 
// Problem: Ex - Odd Steps
// Contest: AtCoder - AtCoder Beginner Contest 258
// URL: https://atcoder.jp/contests/abc258/tasks/abc258_h
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;
const ll mod = 998244353;

ll n, m, a[maxn], f[maxn], g[2];
struct matrix {
	ll a[2][2];
	matrix() {
		mems(a, 0);
	}
} ma, I, ans;

inline matrix operator * (matrix a, matrix b) {
	matrix res;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
			}
		}
	}
	return res;
}

inline matrix qpow(matrix a, ll p) {
	matrix res = I;
	while (p) {
		if (p & 1) {
			res = res * a;
		}
		a = a * a;
		p >>= 1;
	}
	return res;
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	a[n + 1] = m + 1;
	ma.a[0][0] = 2;
	ma.a[0][1] = ma.a[1][0] = ma.a[1][1] = 1;
	I.a[0][0] = I.a[1][1] = 1;
	ans.a[0][0] = 1;
	for (int i = 1; i <= n + 1; ++i) {
		if (a[i] - a[i - 1] <= 5) {
			for (ll x = a[i - 1] + 1; x < a[i]; ++x) {
				ans.a[0][x & 1] = (ans.a[0][x & 1] + ans.a[0][(x & 1) ^ 1]) % mod;
			}
		} else {
			ll x = a[i - 1] + 1;
			if (x % 2 == 0) {
				ans.a[0][x & 1] = (ans.a[0][x & 1] + ans.a[0][(x & 1) ^ 1]) % mod;
				++x;
			}
			matrix t = qpow(ma, (a[i] - x) / 2);
			x += (a[i] - x) / 2 * 2;
			ans = ans * t;
			if (x != a[i]) {
				ans.a[0][x & 1] = (ans.a[0][x & 1] + ans.a[0][(x & 1) ^ 1]) % mod;
			}
		}
	}
	printf("%lld\n", ans.a[0][(m & 1) ^ 1]);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

/*
g[i][1] = g[i - 1][0] + g[i - 1][1]
g[i][0] = g[i - 1][0] + g[i][1] = 2 * g[i - 1][0] + g[i - 1][1]
*/