题目大意：
给你一个长度为 $n$ 的字符串 $s$。
每一次操作，可以选择一个位置（不为最后一位），然后删除它和它后面一位，在原来的位置上填上他们的或。每次操作会使 $n-1$。
问你执行最多 $n-1$ 次操作后能得到多少不同的串。
题解：
根据套路，就可以把相同的数分成一段一段的。又因为是或，所以我们可以认为 $1$ 永远比 $0$ 强，就统计相邻两个 $1$ 之间 $0$ 的个数。（记第 $i$ 段为 $cnt_i$，有 $m$段）
考虑操作过程：
如果选择的是两个 $1$，那么段数会 $-1$，但由于反正间隔都是 $0$ 个 $0$了，我们就可以不用管了。（有问题，后面会提到）
反之，删除的肯定是一个 $0$，就当那一段的 $0$ 个数 $-1$。
然后我们就相当于：统计数组 $a$ 的个数，满足 $a_i \le cnt_i$ 了
吗？
不，这题不会这么简单，因为很显然会重复计算。
所以，我们考虑怎么去重：
前面推的时候，对于选择了两个 $1$ 的情况，很难自圆其说是不是？
我们对这一块重新考虑下。
令 $dp_i$ 表示考虑到 $cnt_i$ 时的方案数。
为了去重，当 $dp_i$ 由 $dp_k$ 转移过来的时候，需要满足对于所有的 $k+1 \le j \le i-1,cnt_j<cnt_i$，这样就限制了多次转移的情况，而且不会使答案遗漏。
处理 $k$ 的话，打个标记就好了。
最后用前缀和优化把复杂度从 $O(n^2)$ 降到 $O(n)$
Code:
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
| string s;
const int mxn=1e6+6;
int cnt[mxn],m,n;
const ll md=1000000007;
ll sum[mxn],dp[mxn];
int pos[mxn];
inline void add(ll&x,ll y){
x+=y;
if(x>=md)x-=md;
if(x<0)x+=md;
if(x>=md)x-=md;
if(x<0)x+=md;
}
inline void solve(){
cin>>s;n=s.size();
s=s+"1";
for(int i=0,j=0;i<s.size();++i){
for(;j<s.size() and s[j]=='0';)++j;
cnt[++m]=j-i;
i=j;
j=i+1;
}
if(m==1){
cout<<n<<'\n';
return;
}
ll ans=(cnt[1]+1)*1ll*(cnt[m]+1)%md;
sum[1]=1,dp[1]=1;
for(int i=1;i<=n;++i)pos[i]=1;
for(int i=2;i<m;++i){
for(int j=0;j<=cnt[i];++j)add(dp[i],sum[i-1]-sum[pos[j]-1]);
for(int j=0;j<=cnt[i];++j)pos[j]=i;
add(sum[i],sum[i-1]+dp[i]);
}
cout<<(ans*1ll*sum[m-1])%md<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
for(;T--;)solve();
return 0;
}
|