【2021牛客OI赛前集训营】与巨

题目来源：2021牛客OI赛前集训营-提高组（第一场） ↗

题意#

定义序列 $f$ ：

f_i= \left\{ \begin{array}{lr} 1,&i=1\\ f_{i-1}\times 2+1, &i>1 \end{array} \right.

定义函数 $G(x)=\min\limits_{f_i\geq x}(f_i)$ .

定义序列 $\operatorname{dp}$ ：

\operatorname{dp}_i= \left\{ \begin{array}{lr} 0,&i=0\\ \max\left\{ \begin{array}{lr} \operatorname{dp}_{i-1}\\ [(i\times c)\&G(i)==i]\times i \end{array} \right\}, &i>0 \end{array} \right.

求 $\sum_{i=0}^n{\operatorname{dp}_i}\bmod 998244353$ .

分析#

直接暴力有 $\rm{20pts}$ .

观察 $f_i$ 的形式， $G(i)$ 一定可以表示为 $2^{t+1}-1,t\in \Bbb{N^*}$ .

把二进制形式写出来， $x\&G(i)$ 等价于 $x\bmod 2^{t+1}$ .

因此，当 $i\in[2^t, 2^{t+1}-1]$ 时：

\begin{array}{ll} & (i\times c) \& G(i)=i\\ \Rightarrow & (i\times c)\bmod 2^{t+1}=i\\ \Rightarrow & i\times (c-1)\equiv0\pmod{2^{t+1}} \end{array}

把 $(c-1)$ 中二的幂次提出来，设 $c-1=2^p\times x$ ，则 $i$ 需要含有因子 $2^{t+1-p}$ ，即 $i\equiv 0\pmod{2^{t+1-p}}$ 。

注意： 有特殊情况，若 $c-1=0$ ，条件恒成立，答案直接就是 $\sum_{i=0}^n{i}$ ，需要单独判断。

设 $m$ 为二进制下 $n$ 的长度 $|n|$ .

考虑枚举上面的 $t$ ，由于 $m$ 位二进制数的取值范围是 $[0, 2^m-1]$ ，而 $G(i)=2^{t+1}-1$ ，因此 $t\in[0, m-1]$ 。

分两种情况讨论。

当 $t\neq m-1$ 时#

$[2^t, 2^{t+1}-1]$ 内的数，最高位都为 $t$ .

$i$ 需要含有因子 $2^{t+1-p}$ ，为了方便表示，设 $g=t+1-p$ .

$i$ 含有 $2^g$ ，这样的数为：

2^t,\quad 2^t+2^g,\quad 2^t+2\cdot 2^g,\quad 2^t+3\cdot 2^g,\cdots,\quad 2^t+x\cdot 2^g

$x$ 就是最后一项的系数，满足 $2^t+(x+1)\cdot2^g=2^{t+1}$ .

上面共有 $x+1$ 项，是等差数列，可以直接求和。

依题意，每个数对答案有 $2^g$ 次贡献，还要对 $\operatorname{sum}$ 乘上 $2^g$ 。

注意： 当 $g=t+1$ ，即 $c\bmod 2=0$ 时，上面的等差数列不存在，答案直接为 $0$ 。为了方便实现，可以在代码的最前面特判这种情况。

当 $t=m-1$ 时#

和上面类似。不过由于 $2^{t+1}>n$ ，在 $[2^t, 2^{t+1}-1]$ 当中有一部分数比 $n$ 大，因此 $x$ 的计算方法需要改变。

具体地，我们需要满足 $2^t+x\times 2^g\leq n$ ，因此， $x=\lfloor\frac{n}{2^g}\rfloor-2^{t-g}$ .

同样地，对这个 $x+1$ 项的等差数列求和，乘上 $2^g$ 加入贡献。

在这个计算方法中，等差数列的最后一项也被计数了 $2^g$ 次，认为其对 $[2^t+x\cdot 2^g, 2^t+(x+1)\cdot 2^g-1]$ 这个范围内都有贡献。

然而区间右端点可能 $>n$ ，所以要减去 $2^t+(x+1)\cdot 2^g-1-n$ 次贡献，每次贡献的值是 $2^t+x\times 2^g$ 。

代码#

注意等差数列求和的时候，要用 $2$ 的逆元代替除法.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXLEN = 1e7 + 10, mod = 998244353, inv2 = 499122177;
int T, m, c;
char s[MAXLEN];
int pow_2[MAXLEN];
inline int calc(int st, int ed, int x) {//首项、末项、项数
	if(x <= 0) return 0;
	return (st + ed) * inv2 % mod * x % mod;
}
void solve_0() {
	int n = 0;
	for(int i = 1; i <= m; i++) n = ((n << 1) + s[i] - '0') % mod;
	printf("%lld\n", n * (n + 1) % mod * inv2 % mod);
}
signed main() {
	pow_2[0] = 1;
	for(int i = 1; i <= 1e7; i++)
		pow_2[i] = (pow_2[i - 1] << 1) % mod;
	scanf("%lld", &T);
	while(T--) {
		scanf("%s%lld", (s+1), &c);
		if(c % 2 == 0) {
			printf("0\n");
			continue;
		}
		if(c - 1 == 0) {
			solve_0();
			continue;
		}
		m = strlen(s + 1); c = c - 1;
		int p = 0, ans = 0;
		while(c != 0 && c % 2 == 0) p++, c /= 2;
		for(int t = 0; t <= m - 1; t++) {
			int g = max(0ll, t + 1 - p);
			//c%2==0的情况在上面处理过了，所以可以像下面这样对等差数列求和
			if(t < m - 1) { //t < m - 1时
				ans += pow_2[g] * calc(pow_2[t], pow_2[t+1]-pow_2[g], pow_2[t+1-g]-pow_2[t-g]) % mod;
				ans %= mod;
			} else { //t = m - 1时
				//n/(2^g)下取整，也就是二进制下左边的前n-g位的值
				int x = 0;
				for(int i = 1; i <= m - g; i++)
					x = ((x << 1) + s[i] - '0') % mod;
				x = (x + mod - pow_2[t - g]);
				ans += pow_2[g] * calc(pow_2[t], (pow_2[t] + x * pow_2[g]) % mod, x + 1);
				ans %= mod;
				int n = 0, r = (pow_2[t] + (x + 1) * pow_2[g] % mod - 1) % mod;
				for(int i = 1; i <= m; i++)
					n = ((n << 1) + s[i] - '0') % mod;
				ans -= (r - n) * (pow_2[t] + x * pow_2[g] % mod) % mod;
				ans %= mod;
			}
		}
		ans = (ans + mod) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}

cpp

题意#

分析#

当 t≠m−1t\neq m-1t=m−1 时#

当 t=m−1t=m-1t=m−1 时#

代码#

当 $t\neq m-1$ 时#

当 $t=m-1$ 时#