快跟我一起 ctj 吧
\(\textsf{C tj}\) 兔已着陆/九月的南瓜
原题链接
比赛题目链接
题目大意
构造一个长度为 \(n\) 的 \(01\) 串，回答以下两个问题：
- 问题 \(1\)：存在一个长度为 \(m\) 的全 \(1\) 子串的构造方案数。
- 问题 \(2\)：恰好有一个长度为 \(m\) 的全 \(1\) 子串的构造方案数。
\(n,m \le 10^7\)。
思路
又是一道 \(\texttt{dp}\) 用数学水的题。
我们设 \(S(x,y)\) 表示问题 \(1\)。（\(x\) 代指 \(m\)，\(y\) 代指 \(n\)，\(S(m,n)\) 为最终答案）
再设 \(T(x,y)\) 表示问题 \(2\)。（\(T(m,n)\) 为最终答案）
发现 \(O(n)\) 是可以过的，可以递推。
求 \(S\)
我们先画一张图：
什么意思呢？
\(S(m,i)\) 有两种情况：
- 如果前 \(i-1\) 个成立，第 \(i\) 个数可以随便填。
- 如果前 \(i-m-1\) 个不成立，但是尾部为 \(m-1\) 个 \(1\)，所以再添一个 \(1\)，就又是一种构造方案。
前 \(i-1\) 个成立的方案数，即为 \(S(m,i-1)\)。
前 \(i-m-1\) 个不成立的方案数，就是总方案数减去前 \(i-m-1\) 个成立的方案数。
又因为每个位置都有 \(0,1\) 两种可能，所以总方案数为 \(2^{i-m-1}\)。
于是前 \(i-m-1\) 个不成立的方案数为 \(2^{i-m-1} - S(m,i-m-1)\)。
综上所述，
求 \(T\)
我们再画一张图：
为什么是 \(S\) 不成立，而不是 \(T\) 不成立？
因为 \(T\) 不成立有可能是长度为 \(m\) 的全 \(1\) 子串，不符合我们的期望。
\(T(m,i)\) 后面可以填 \(0/1\)。但有几种限制。
- 如果前 \(i-m-2\) 不成立，但最后有 \(m\) 个 \(1\)。则不能再放 \(1\)。
- 如果前 \(i-m-1\) 成立，且最后有 \(m-1\) 个 \(1\)，则也不能再放 \(1\)。
- 如果前 \(i-m-1\) 不成立，最后有 \(m-1\) 个 \(1\)，所以再添一个 \(1\)，就又是一种构造方案。
综上所述，
简化+注意事项
这样的时间复杂度还是 \(O(n\log n)\) 的。
于是我们预处理出 \(2^x\)。就可以优化到 \(O(n)\)。
但是我们的式子加上取模后就又臭又长。所以定义 \(F(m,i)\) 表示 \(S(m,i)\) 不成立。
但是 \(T\) 的转移有可能访问到 \(F(m,-1)\)。此时应该返回 \(1\)。（考试时就是因为这个挂了）
所以：
于是 \(S\) 和 \(T\) 就可以简化成：
于是就写完了。
\(\textsf{code}\)
#include
#define int long long
using namespace std;
const int N = 1e7+10;
const int mod = 998244353;
int S[N], T[N], mi[N], n, m;
int F(int x){ return x < 0 ? 1 : (mi[x] - S[x] + mod) % mod; }
signed main(){freopen("seiran.in","r",stdin);freopen("seiran.out","w",stdout);cin >> n >> m;S[m] = 1, T[m] = 1, mi[0] = 1;for(int i = 1; i <= n; i++) mi[i] = mi[i-1] * 2 % mod;for(int i = m+1; i <= n; i++){S[i] = (2 * S[i-1] % mod + F(i-m-1)) % mod;T[i] = (2 * T[i-1] % mod - F(i-m-2) - T[i-m-1] + mod + F(i-m-1)) % mod;}cout << S[n] << '\n' << T[n];return 0;
}
然后你就可以愉快地 \(\green{\textsf{AC}}\) 了！
菜鸭好菜，菜鸭不会 DP，菜鸭只会数学。。。