ABC305G Banned Substrings

博主： Skykguj
发布时间：2023 年 06 月 15 日
36 次浏览
暂无评论
2334字数
分类：竞赛相关

> 给定 $m$ 个由 $0$ 和 $1$ 构成的字符串，长度最多是 $6$。<template style="display: block; margin-top: -15px"></template>
> 求有多少种长度为 $n(n \le 10^{18})$ 的 $01$ 字符串，其子串不包括这 $m$ 个字符串。

我们预处理出长度 $1 \sim 6$ 的所有合法 $01$ 串，考虑状压 DP，设字符串的长度为阶段，$dp[i][s]$ 表示长度为 $i$ 的字最近的 $6$ 位状态为 $s$ 的合法字符串个数。

我们设 $s_1$ 为新的一位选择 $1$，$s_2$ 为新的一位选择 $0$，那么有转移方程：

$$
\begin{cases}f[i][s1] = f[i][s1] + f[i-1][j], j \in states \\f[i][s2] = f[i][s2] + f[i-1][j], j \in states\end{cases}
$$

转移时要注意状态合法。

注意到 $n \le 10^{18}$，普通的状压 DP 会超时，我们可以利用矩阵来加速转移。

设 $c_s$ 表示状态 $s$，$p_{i,j}$ 由状态 $i$ 转移为状态 $j$ 的方案数，则有转移：

$$
f = \begin{bmatrix}c_{s_1} & c_{s_2} & \cdots & c_{s_{tot}}\end{bmatrix}\times\begin{bmatrix}p_{s_1, s_1} & p_{s_2, s_1} & \cdots & p_{s_{tot}, s_1} \\p_{s_1, s_2} & p_{s_2, s_2} & \cdots & p_{s_{tot}, s_2} \\t\vdots & \vdots & \ddots & \vdots \\p_{s_1, s_{tot}} & p_{s_2, s_{tot}} & \cdots & p_{s_{tot}, s_{tot}}\end{bmatrix}^{n-6}
$$

实现代码：

#include <bits/stdc++.h>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    #define int long long
    
    inline int read() {
    	int x = 0, f = 1; char ch = getchar();
    	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
    	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    	return x * f;
    }
    
    const int N = 130, M = 100010;
    const int mod = 998244353;
    
    int n, m, f[M][N];
    bool check[N];
    pair<PII, int> a[N];
    
    struct Mat {
    	int a[130][130];
    	void print() {
    		for (int i = 0; i < 64; i ++ ) {
    			for (int j = 0; j < 64; j ++ ) {
    				printf("%lld ", this->a[i][j]);
    			}
    			puts("");
    		}
    	}
    	void operator*= (const Mat b) {
    		auto tmp = *this;
    		for (int i = 0; i < 64; i ++ ) {
    			for (int j = 0; j < 64; j ++ ) {
    				this->a[i][j] = 0;
    			}
    		}
    		for (int k = 0; k < 64; k ++ ) {
    			for (int i = 0; i < 64; i ++ ) {
    				for (int j = 0; j < 64; j ++ ) {
    					this->a[i][j] = (this->a[i][j] + tmp.a[i][k] * b.a[k][j] % mod) % mod;
    				}
    			}
    		}
    	}
    	Mat operator* (const Mat b) {
    		Mat c;
    		memset(c.a, 0, sizeof c.a);
    		for (int k = 0; k < 64; k ++ ) {
    			for (int i = 0; i < 64; i ++ ) {
    				for (int j = 0; j < 64; j ++ ) {
    					c.a[i][j] = (c.a[i][j] + this->a[i][k] * b.a[k][j] % mod) % mod;
    				}
    			}
    		}
    		return c;
    	}
    } tp, p, res;
    
    int convert(string s, char ch) {
    	int res = 0, len = s.length();
    	for (int i = 0; i < len; i ++ ) res = res * 2 + (s[i] == ch);
    	return res;
    }
    
    void init(Mat &res) {
    	for (int i = 0; i < 64; i ++ ) {
    		res.a[i][i] = 1;
    	}
    }
    
    signed main() {
    	n = read(), m = read();
    	string tmps;
    	for (int i = 1; i <= m; i ++ ) {
    		cin >> tmps;
    		int t1 = convert(tmps, 'b'), t2 = convert(tmps, 'a');
    		a[i] = {{t1, t2}, tmps.size()};
    	}
    	int mxl = min(n, 6ll), tot = (1 << mxl);
    	for (int i = 0; i < tot; i ++ ) {
    		check[i] = true;
    		for (int k = 1; k <= m; k ++ ) {
    			int s1 = a[k].first.first, s2 = a[k].first.second;
    			int nowlen = a[k].second;
    			for (int j = nowlen - 1; j < mxl; j ++ ) {
    				if (((i & s1) == s1) && ((i & s2) == 0)) check[i] = false;
    				s1 <<= 1, s2 <<= 1;
    			}
    		}
    		// 未优化 dp
    		if (check[i]) f[mxl][i] = 1;
    	}
    	if (n <= 1e5) {
    		for (int i = mxl; i <= n; i ++ ) {
    			for (int s = 0; s < tot; s ++ ) {
    				for (int c = 0; c < 2; c ++ ) {
    					int j = (s << 1) | c;
    					j &= tot - 1;
    					if (!check[s] || !check[j]) continue;
    					f[i][j] += f[i - 1][s];
    				}
    			}
    		}
    		int ans = 0;
    		for (int i = 0; i < tot; i ++ ) {
    			ans += f[n][i] * check[i];
    		}
    		printf("%lld\n", ans);
    	}
    	else {
    		for (int s = 0; s < tot; s ++ ) {
    			for (int c = 0; c < 2; c ++ ) {
    				int j = (s << 1) | c;
    				j &= tot - 1;
    				if (!check[s] || !check[j]) continue;
    				p.a[j][s] += 1;
    			}
    		}
    		for (int s = 0; s < tot; s ++ ) {
    			if (!check[s]) continue;
    			tp.a[0][s] = 1;
    		}
    		init(res);
    		int k = n - mxl, ans = 0;
    		for (; k; k >>= 1) {
    			if (k & 1) res *= p;
    			p *= p;
    		}
    		res = tp * res;
    		for (int s = 0; s < tot; s ++ ) ans = (ans + res.a[0][s]) % mod;
    		printf("%lld\n", ans);
    	}
    	return 0;
    }

最后修改：2023 年 07 月 06 日

赠人玫瑰，手有余香。您的赞赏是对我最大的支持!

发表评论取消回复
使用 cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

ABC305G Banned Substrings

发表评论取消回复
使用 cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Typecho Handsome 主题显示实时在线人数

VMware Workstation Player 15.5 安装教程（附注册机）

LNMP 一键安装包部署 Django 项目

几款主流并且好用的 Markdown 编辑器一览

水仙花数 -- C++ 实现

数字逆序输出 -- C++ 实现

ProcessOn 免费在线绘图工具的介绍和基本使用

Manacher（马拉车）算法学习笔记

基环树思路总结

1788：Pell 数列 -- C++ 递推法

ABC305G Banned Substrings

发表评论 取消回复 使用 cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

ABC305G Banned Substrings

发表评论取消回复
使用 cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款