CodeForces - 1762C Binary Strings are Fun

Posted on | In ,

题意

我们定义一个01字符串是good当且仅当每个奇数位index的数字是1-index这个子串的中位数（即这个数字是1-index子串中出现最多的数字）。定义extend操作为对于一个01串，在两两数字之间插入0/1.现给定一个01串，问对于所有的前缀，extend后为good的串有多少。

解法

首先我们能够得到以下两个结论：

  1. 我们首先考虑一个全为0的字符串，长度为k。如果我们要扩展这个字符串，那么对k-1个空我们能够随便填写，因为不论我们怎么填0都已经必然是出现次数最多的，所以答案为2^(k-1)。
  2. 现在我们考虑有不同字符的01串。首先我们能够发现，如果是01这种相邻不一样的串，在extend时必须插入1。所以对于这种相邻不一样的串，我们能插入的串是固定的。

基于上述结论，假定我们的初始01串为…01（长度k），那么我们就能够反推出唯一的一个extend good串。对于长度为k-1，0结尾的前缀，由于它是一个good串，那么extend后的串中应该有k-1个0，也就是至多k-2个1。对于长度为k，1结尾的前缀，由于他extend后是good，所以extend后的串至少有k个1，在结尾已经有一个1，前面至多k-2个1的情况下，不难知道，0和1中必须放入1.同时，这个结论是能向前递推的，不论之前的串是相同的还是不同的，有兴趣的可以自己推一下，这里不再赘述。

基于上述讨论，我们能够知道，一个01/10这种相邻不同的串就能让最后一位的统计还原为1，同时如果是11，00这种相邻一样的串，每次答案都是上一个答案的2倍。所以最终的算法为，从头开始计算，如果当前数字和上一个一样，计数器变为2倍，否则计数器重制为1.对每一位的计数器累加就是答案。

代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// This template is based on tourist's template<Modular>
// Used for modular calculation
template <typename T>
T inverse(T a, T mod) {
    T u = 0, v = 1;
    while(a) {
        T t = mod/a;
        mod -= t*a; swap(a, mod);
        u -= t*v; swap(u, v);
    }
    return u;
}
template <typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;
    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
        value = normalize(x);
    }
    Modular(const Modular &x) {
        value = x.value;
    }
    template <typename U>
    static Type normalize(const U &x) {
        Type v;
        if(-mod() <= x && x<mod()) {
            v = static_cast<Type>(x);
        } else {
            v = static_cast<Type>(x%mod());
        }
        if(v < 0) {
            v += mod();
        }
        return v;
    }
    constexpr static Type mod() {
        return T::value;
    }
    const Type& operator ()() const {
        return value;
    }
    template <typename U>
    explicit operator U() const {
        return static_cast<U>(value);
    }
    Modular& operator +=(const Modular& other) {
        if((value+=other.value)>=mod()) {
            value-=mod();
        }
        return *this;
    }
    Modular& operator -=(const Modular& other) {
        if((value-=other.value)<0) {
            value+=mod();
        }
        return *this;
    }
    template <typename U>
    Modular& operator +=(const U& other) {
        return *this+=Modular(other);        
    }
    template <typename U>
    Modular& operator -=(const U& other) {
        return *this-=Modular(other);    
    }
    Modular& operator++(){
        return *this+=1;
    }
    Modular& operator--() {
        return *this-=1;
    }
    Modular operator++(int) {
        Modular result(*this);
        *this+=1;
        return result;
    }
    Modular operator--(int) {
        Modular result(*this);
        *this-=1;
        return result;
    }
    Modular operator-() const {
        return Modular(-value);
    }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(static_cast<int64_t>(value)*static_cast<int64_t>(rhs.value));
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
        long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator /=(const Modular& other) {
        return *this*=Modular(inverse(other.value, mod()));
    }
    friend const Type& abs(const Modular& x) {
        return x.value;
    }
    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
 
    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
 
    template <typename V, typename U>
    friend V& operator>>(V& stream, Modular<U>& number);

//private:
    Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
 
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
 
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
 
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
 
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
 
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
 
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
    return number() == 0;
}
 
template <typename T>
string to_string(const Modular<T>& number) {
    return to_string(number());
}
 
// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
    return stream << number();
}
 
// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, long long>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
 
Mint C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  }
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}


void solve() {
    int n;
    cin>>n;
    string str;
    cin>>str;
    int last = -1;
    Mint ans(0);
    Mint cnt(1);
    for(int i = 0; i < n; i++) {
        int cur = str[i]-'0';
        if(cur!=last) {
            last = cur;
            cnt = 1;
        } else {
            cnt*=2;
        }
        ans+=cnt;
    }
    cout<<ans<<endl;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("./input.txt","r",stdin);
    freopen("./output.txt","w",stdout);
#endif // ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--) {
      solve();
    }
    return 0;
}