进位 / carry
Mier_Samuelle
·
·
题解
竞选全场最劣解。
考虑 dp。设 f_i 为以 i 结尾的 p 的个数。对每个 i，设 [l_i,r_i] 为使 C(i,j)=1 的 j 的区间。那么对每个 j \in [l_i,r_i]，有转移 f_i \rightarrow f_j。这是一段区间加，树状数组可以维护。
接下来考虑求 l_i,r_i。发现若跳过所有 0，则至多枚举 2 \cdot \log V \approx 80 个数就能找到 r_i，因为每次不进位至少使一个 0 变成 1。但这样还是有点劣，考虑双指针求出 l_i，然后从 l_i 往后枚举，这样就只会枚举 \log V \approx 40 个数，可以通过。
复杂度 $O(n \log V+n \log n)$。
:::success[Code]{open}
```cpp
#include <bits/stdc++.h>
#define popcnt __builtin_popcountll
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int MOD = 998244353;
ll a[MAXN];
int nxt[MAXN], ra[MAXN], rb[MAXN], n;
inline void add(ll &x, ll y){
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
return;
}
struct BIT{
ll v[MAXN];
void init(){
for (int i = 1; i <= n; i++){
v[i] = 0;
}
return;
}
int lowbit(int x){
return x & (-x);
}
void modify(int u, ll x){
while (u <= n){
add(v[u], x);
u += lowbit(u);
}
return;
}
ll query(int u){
ll res = 0;
while (u){
add(res, v[u]);
u -= lowbit(u);
}
return res;
}
}tr;
void solve(){
cin >> n;
for (int i = 1; i <= n; i++){
nxt[i] = ra[i] = rb[i] = 0;
}
for (int i = 1; i <= n; i++){
cin >> a[i];
}
int cur = n + 1;
for (int i = n; i >= 1; i--){
nxt[i] = cur;
if (a[i]){
cur = i;
}
}
ll sum = 0;
for (int l = 1, r = 1; l <= n; sum -= a[l], l++){
while (r <= n && (sum & a[r]) == 0){
sum += a[r];
r++;
}
if (popcnt(sum) + popcnt(a[r]) - popcnt(sum + a[r]) > 1){
ra[l] = n + 1;
rb[l] = n;
continue;
}
ra[l] = r;
if (ra[l] > n){
rb[l] = n;
continue;
}
ll psum = sum + a[r];
for (int u = nxt[r]; u <= n; u = nxt[u]){
if (psum & a[u]){
rb[l] = u - 1;
break;
}
psum += a[u];
}
if (!rb[l]){
rb[l] = n;
}
}
tr.init();
ll ans = 0;
for (int i = 1; i <= n; i++){
tr.modify(i, 1);
tr.modify(i + 1, -1);
ll val = tr.query(i);
if (ra[i] <= rb[i]){
tr.modify(ra[i], val);
tr.modify(rb[i] + 1, -val);
}
ans += val;
if (ans >= MOD) ans -= MOD;
}
cout << ans << "\n";
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
```
:::