一道很神仙的结论题，很考验观察能力
题目链接。
题意
给定一个长度为 的
串，可以进行若干次操作，每一次操作是选择一个长度为
的子串，并将这个串替换为三个数的中位数。
问可以得到多少种不同的串，对 取模。
数据组数 。。
题解
首先转换一下这个操作，其实相当于，要么选择两个相邻的不同数然后删掉（要求删完之后串非空），或者对于三个相邻相同的数，删掉其中两个。
然后下面是题解中需要用到的一些小结论。
引理 ：对于一个长度为奇数的子串，存在方案把他删成只剩
位。
证明：显然，若存在两种数字，则可以进行第一种操作，否则可以进行第二种操作，删到只剩一位为止。
引理 ：对于一个长度为偶数的区间
，若 ，则区间 可以被删空
证明：根据引理 ，区间 能被删成只剩一位。
此时若这一位与
不相同，则可以用操作
把这两个一块删掉。
否则剩余的三个数字相同，可以用操作 删掉。
同理，若将条件换为 ，则区间 也可以被删空。
称原串为 ，考虑能否通过操作变成某个串 。
根据一些做题的套路，我们应该要对 的每一位在 上做贪心匹配。
具体来说，对于一个点 ，他有两条出边 ，出边 连向比 大的最小的满足 且 可以删空的最小的 。
假如我们能建出这个自动机，我们统计到的答案一定是能变出的串。
那么如何证明所有能变出的串都会被统计上呢？其实只需要证明每一次转移最小的
是最优的就好了。
假设有三个位置 满足
且
都能删空，那么只需要证明对于任意一个 ，若 能删空则 能删空即可。
容易发现，若
能够被删空，则上述条件自然成立，而这恰好是引理 的内容。
所以这个自动机一定可以算出所有合法的答案，现在问题在于如何建出这个自动机。
对于一个点 来说，连向的点
下标一定和 奇偶性不同，所以这部分后文默认 且 奇偶性不同。
假设 。
对于 边来说， 一定是最小的位置满足 。因为 前面全都是 ，所以区间 一定可以删空。
对于 边来说， 是最小的位置满足 。根据引理 ，区间 可以被删空。
当然我们还需要证明对于 且 ，区间 删不空。
这是容易的，注意到删到最后一定会有两个 相邻（并且左边的 位置与 同奇偶）。而如果进行操作之前没有 相邻，操作之后也不会有 相邻。
而 是最小的位置满足 ，所以前面的 一定删不空。
这样我们就能在
复杂度对一个串建出这个自动机。
现在还有一点问题，就是我们连好了中间的边，但是没有确从点
连出的边，以及哪些位置可以被统计入答案。
先来考虑第二个问题。
这相当于我们需要知道，对于每一个和 同奇偶的位置 ， 能不能删空。
首先，若 ，则根据引理
，区间一定可以被删空。
所以只需要考虑
的情况。
观察可以发现，可以删空等价于存在与 不同奇偶的位置 满足 。
证明如下：
根据上面的讨论，若条件满足，则区间 能删空，根据引理 可以知道区间 一定也可以删空。
若条件不满足，考虑在
位置补一个虚点，上面的数字是 。
首先可以知道 与
不同奇偶，根据上面自动机的讨论，在补完这个位置之后，
删不空，所以不补这个位置的时候， 一定也删不空。
这样就证完了。
开头的问题和结尾基本一样，要注意的是开头两种边只能各连一条。
时间复杂度 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
int nx1[5000005][2];
int nx2[5000005][2];
ll f[5000005];
char s[5000005];
int n;
inline void Add(ll &a,ll b)
{
a+=b;
if(a>=mod) a-=mod;
}
inline void solve()
{
scanf("%s",s+1),n=strlen(s+1);
memset(nx1,0,sizeof(nx1));
memset(nx2,0,sizeof(nx2));
memset(f,0,sizeof(f));
nx1[n+1][0]=nx1[n+1][1]=nx2[n+1][0]=nx2[n+1][1]=n+1;
nx1[n+2][0]=nx1[n+2][1]=nx2[n+2][0]=nx2[n+2][1]=n+2;
for(int i=n;i;i--)
{
nx1[i][0]=nx1[i+2][0],nx1[i][1]=nx1[i+2][1];
nx2[i][0]=nx2[i+2][0],nx2[i][1]=nx2[i+2][1];
nx1[i][s[i]-'0']=i;
if(i!=1&&s[i]==s[i-1]) nx2[i][s[i]-'0']=i;
}
f[1]=1;ll ans=0;
for(int i=3;i<=n;i+=2) if(s[i]!=s[1]&&s[i]==s[i-1]){ f[i]=1;break;}
for(int i=1;i<=n;i++)
{
int p=s[i]-'0';
if(nx1[i+1][!p]<=n) Add(f[nx1[i+1][!p]],f[i]);
if(nx2[i+1][p]<=n) Add(f[nx2[i+1][p]],f[i]);
if((n-i)%2==0&&(s[i]==s[n]||nx2[i+1][p]<=n)) Add(ans,f[i]);
}
printf("%lld\n",ans);
}
int main()
{
int T=read();
while(T--) solve();
return 0;
}
|