题目描述
http://codeforces.com/gym/102956/problem/C
Solution
我们令 $f_i$ 为最后一位填 $i$ 的方案数，显然 $ans=\sum_{i=1}^nf_i$
令 $k,j,i$ 为从左到右的三个相邻的位置的数字
显然当 $i\oplus j=k$ 时，$k,j,i$ 不合法，那么能够得到转移 $f_i=\sum_{j=0}^{i-1}f_j-f_{i\oplus j}[i\oplus j<j]$
令 $maxbit(v)$ 表示$v$ 的二进制最高位，注意到 $k<i<j$，那么一定满足 $maxbit(i)=maxbit(j)$
那么我们根据这个东西去枚举小于 $i$ 的 $j$，然后发现 $i\oplus j$ 是 $log$ 个区间，于是我们再维护一个前缀和
时间复杂度 $O(n\log n)$
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
| #include <iostream>
#include <cmath>
#include <vector>
#define maxn 1000010
#define ll long long
using namespace std;
const int p = 998244353;
int n;
ll f[maxn], s[maxn];
ll get(int l, int r) { return s[r] - s[l - 1]; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
int o = 0; f[i] = s[i - 1] + 1;
for (int j = 20; ~j; --j)
if (i >> j & 1) { o = j; break; }
for (int j = o - 1; ~j; --j)
if (i >> j & 1)
f[i] = (f[i] - get(1 << j, (1 << j + 1) - 1)) % p;
s[i] = (s[i - 1] + f[i]) % p;
} cout << (s[n] + p) % p << "\n";
return 0;
}
|