• 欢迎光临~

ABC258Ex

开发技术 开发技术 2022-10-23 次浏览

考虑答案实际就是从 (T=left{0,1,cdots,Sright}setminus left{A_1,cdots,A_Nright}) 中选取若干个数并且满足以下条件:

  • (0)(S) 一定要选。
  • 当选的数从小到大排列时,相邻两个数的奇偶性不同。

先考虑 (mathcal O(S)) 的暴力 DP。

先忽略一定要选 (S) 这个条件,设 (f_{i,j}) 表示在 (T) 中选不超过 (i) 的数,选的最大数模 (2) 余数为 (j) 的方案数。

每次 (i)(i+1) 转移。

  • 如果不选 (i+1),那么 (f_{i+1,j}gets f_{i+1,j}+f_{i,j},j=0,1)
  • 否则如果 (i+1in T),可以选 (i+1),那么 (f_{i+1,j}gets f_{i+1,j}+f_{i,1-j})(j)(i+1)(2) 的余数。

最后考虑 (S) 一定要选这个条件,那么就是 (f_{S-1,1-j})(j)(S)(2) 的余数。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, mod = 998244353;
int n; ll S;
bool vis[N];
int f[N][2];

void add(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}

int main() {
	scanf("%d%lld", &n, &S);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), vis[x] = 1;
	f[0][0] = 1;
	for (int i = 0; i < S - 1; ++i) {
		add(f[i + 1][0], f[i][0]), add(f[i + 1][1], f[i][1]);
		if (!vis[i + 1]) add(f[i + 1][(i + 1) & 1], f[i][1 - ((i + 1) & 1)]);
	}
	printf("%d", f[S - 1][1 - (S & 1)]);
	return 0;
}

怎么优化呢?考虑在相邻两个 (A_i) 之间,有很多重复的相同的转移,这是很浪费的,自然想到矩阵快速幂。

但是上面的状态不能这样优化,考虑换一个状态。

(f_{i,j}) 表示在 (T) 中选取不超过 (i) 的数,选的最大数的奇偶性和 (i+j) 相同的方案数。

那么转移变成了:

  • (f_{i+1,0}gets f_{i+1,0}+f_{i,1},f_{i+1,1}gets f_{i+1,1}+f_{i,0})
  • 如果 (i+1in T),那么 (f_{i+1,0}gets f_{i+1,0}+f_{i,0})

那么对于大段的 (i+1in T),则有 (begin{pmatrix} f_{i+1,0} & f_{i+1,1} end{pmatrix}=begin{pmatrix} f_{i,0} & f_{i,1} end{pmatrix}begin{pmatrix} 1&1 \ 1&0 end{pmatrix})

否则对于 (i+1notin T),就暴力转移。

最终答案为 (f_{S-1,0})

时间复杂度 (mathcal O(nlog S))

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, mod = 998244353;
int n; ll S;
ll a[N];
struct mat {
	int a[2][2];
	
	mat operator * (const mat &x) const {
		mat res; memset(res.a, 0, sizeof res.a);
		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] + 1ll * a[i][k] * x.a[k][j] % mod) % mod;
		return res;
	}
} trans, f;

mat qpow(mat x, ll y) {
	mat res; memset(res.a, 0, sizeof res.a);
	res.a[0][0] = res.a[1][1] = 1;
	while (y) {
		if (y & 1) res = res * x;
		x = x * x;
		y >>= 1; 
	}
	return res;
}

int main() {
	scanf("%d%lld", &n, &S);
	for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
	trans.a[0][0] = trans.a[0][1] = trans.a[1][0] = 1, trans.a[1][1] = 0;
	memset(f.a, 0, sizeof f.a); f.a[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		f = f * qpow(trans, a[i] - a[i - 1] - 1);
		ll val = f.a[0][0];
		f = f * trans;
		f.a[0][0] = (f.a[0][0] - val + mod) % mod;
	}
	f = f * qpow(trans, S - a[n] - 1);
	printf("%lld", f.a[0][0]);
	return 0;
}
程序员灯塔
转载请注明原文链接:ABC258Ex
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com