hihoCoder Challenge 31 C - Good 01-Sequence

题目大意

对 $01$ 串 $S$ 定义函数 $f(S)$,表示一个最小的整数 $k$,使得 $S$ 可以表示成 $k$ 个 $01$ 串的拼接($S=t_1t_2…t_k$),且每一个 $01$ 串 $t_i$ 的逆序对数都是奇数。特殊地,如果不存在任何一种合法的划分方案,则定义 $f(S)=0$。
现在给定一个 $01$ 串 $S$,请求出其所有非空子序列的 $f$ 值之和。

$1\leq|S|\leq10^5$


题目分析

先考虑 $f(S)$ 的取值有哪些可能。
可以发现当 $k\geq3$ 的时候,任意三个连续的 $t_i$ 必须满足最前面的那一段 $1$ 的个数是奇数(否则前三段的逆序对数和后两段的逆序对数奇偶性会不同,段数并不是最优),第二段 $0$ 的个数一定是偶数(否则前两段的逆序对数就是奇数)。
因此,当 $k\geq4$ 时,$t_1t_2t_3$ 和 $t_2t_3t_4$ 都满足这样的关系,此时可以发现 $t_1t_2t_3$ 的逆序对数一定是奇数,段数不是最优。也就是说 $k$ 一定小于等于 $3$。
有了这个性质,我们可以考虑 dp 套 dp,令 $f_{i,j,k,s_1,s_2}$ 表示当前做到第 $i$ 位,选择了的所有数中 $1$ 个数的奇偶性是 $j$,总的逆序对数的奇偶性是 $k$,如果选到了第二段,第二段当前 $1$ 的个数奇偶性为 $0/1$,逆序对个数奇偶性为 $0/1$ 是否可行(一个$2^4$的二进制状态 $s_1$,第三段状态 $s_2$ 同理)的方案数,显然有了这些信息我们就足够分析一种子序列对答案的贡献。
转移和统计答案都很简单。
时间复杂度 $O(n\times 2^{16})$(若干常数就不分析了)。


代码实现

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int P=1000000007;

inline void add(int &x,int y){x=x+y>=P?x+y-P:x+y;}

const int N=100005;
const int L=4;

int f[2][2][2][1<<L][1<<L];
char str[N];
int n,ans;

void dp()
{
f[1][0][0][0][0]=1;
for (int i=0;i<n;++i)
{
bool tar=i&1,src=tar^1;
memset(f[tar],0,sizeof f[tar]);
for (int one=0;one<2;++one)
for (int inv=0;inv<2;++inv)
for (int s=0;s<1<<L;++s)
for (int s_=0,tmp;s_<1<<L;++s_)
if (tmp=f[src][one][inv][s][s_])
{
//skip this digit
add(f[tar][one][inv][s][s_],tmp);
//select this digit
int one_=one^(str[i]-'0'),inv_=inv^(str[i]=='0')*one;
// start the second block
int ds=0;
if (inv&1) ds=1<<str[i]-'0';
// continue the second block
for (int j=0,one__,inv__;j<L;++j)
if (s>>j&1)
{
one__=j&1,inv__=j>>1;
one__=one__^(str[i]-'0');
inv__=inv__^(str[i]=='0')*one__;
ds|=1<<(inv__<<1|one__);
}
// start the third block
int ds_=0;
for (int j=2;j<L;++j) if (s>>j&1) ds_|=1<<str[i]-'0';
// continue the third block
for (int j=0,one__,inv__;j<L;++j)
if (s_>>j&1)
{
one__=j&1,inv__=j>>1;
one__=one__^(str[i]-'0');
inv__=inv__^(str[i]=='0')*one__;
ds_|=1<<(inv__<<1|one__);
}
add(f[tar][one_][inv_][ds][ds_],tmp);
}
}
}

void calc()
{
ans=0;
for (int one=0;one<2;++one)
for (int inv=0;inv<2;++inv)
for (int s=0;s<1<<L;++s)
for (int s_=0,tmp,k;s_<1<<L;++s_)
if (tmp=f[n&1^1][one][inv][s][s_])
{
k=4;
for (int j=2;j<L;++j) if (s_>>j&1){k=3;break;}
for (int j=2;j<L;++j) if (s>>j&1){k=2;break;}
if (inv&1) k=1;
k*=k!=4;
add(ans,1ll*tmp*k%P);
}
}

int main()
{
freopen("seq.in","r",stdin),freopen("seq.out","w",stdout);
scanf("%s",str),n=strlen(str);
dp(),calc(),printf("%d\n",ans);
fclose(stdin),fclose(stdout);
return 0;
}