与巨
题目链接:nowcoder 225876
题目大意
问你有多少个 1~n 的数满足它乘上一个 c 之后它原来不是前导 0 的位跟之前一样。
思路
首先它只要留下前面的一些位,那我们可以相当于它是一个取模操作。
(如果是 (t) 位,那就是 (mod (2^{t+1})))
然后我们进行一个推式子:
(i*cmod(2^{t+1})=i)
(i*(c-1)=0mod(2^{t+1}))
那我们可以找到最低位的 (1),表示成 (2^px)。
然后 (i) 就一定要有 (2^{t+1-p}) 这个因子。
然后设 (g=t+1-p),然后我们考虑枚举 (t),进行一个类似数位 DP 的感觉。
如果 (t<m-1)((n) 最大 (m) 位),那你就是随便选的。
那每次会满足的就分别是 (2^t,2^t+2^g,2^t+2*2^g,...,2^t+x2^g(2^t+(x+1)2^g=2^{t+1}))
然后 (x=2^{t+1}-2^g),每次多了 (2^g),这个是一个等差序列,可以很快求和。
(然后别忘了每次会满足的会贡献 (2^g) 次,所以要乘上 (2^g))
然后考虑 (t=m-1),那我们考虑能选多少。
我们要满足:(2^t+x2^gleqslant n)
然后通过移项等可以得到:(x=leftlfloor dfrac{n}{2^g}
ight
floor-2^{t-g})
然后也是一个等差序列计算,但是你会发现最后移项不一定是计算 (2^g) 次。
它的计数范围是 ([2^t+x2^g,2^t+(x+1)2^g-1]),然后实际要的是 (n),多了 (2^t+(x+1)2^g-1-n) 次。
然后就减去这些的贡献,记得要乘上 (2^t+x2^g),就是 ((2^t+(x+1)2^g-1-n)(2^t+x2^g))。
然后就好啦。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
#define mo 998244353
using namespace std;
int T, m, c, p;
char n[10000001];
ll ans, two[10000001], inv2;
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
ll inv(ll x) {
return ksm(x, mo - 2);
}
ll clac(ll s, ll t, ll n) {//三个分别是首项,尾项,个数
return (s + t) % mo * n % mo * inv2 % mo;
}
int main() {
two[0] = 1;
for (int i = 1; i <= 10000000; i++)
two[i] = two[i - 1] * 2 % mo;
inv2 = inv(2);//预处理出 2 的逆元,每次都要 log 会超时
scanf("%d", &T);
while (T--) {
scanf("%s %d", n + 1, &c);
m = strlen(n + 1);
c--;
if (!c) {
ll re = 0;
for (int i = 1; i <= m; i++) {
re = re * 2 + n[i] - '0';
re %= mo;
}
printf("%lld
", (re + 1) * re % mo * inv2 % mo);
continue;
}
if (c & 1) {
printf("0
");
continue;
}
p = 0;
while (!(c & 1)) {
p++;
c >>= 1;
}
ans = 0;
for (int t = 0; t < m - 1; t++) {
int g = max(0, t + 1 - p);
ans = (ans + two[g] * clac(two[t], (two[t + 1] - two[g] + mo) % mo, two[t - g])) % mo;
ans %= mo;
}
int t = m - 1;
ll N = 0;
int g = max(0, (m - 1 + 1) - p);
for (int i = 1; i <= m - g; i++)
N = ((N << 1) + n[i] - '0') % mo;
N = (N - two[t - g] + 1 + mo) % mo;
ans = ans + two[g] * clac(two[t], (two[t] + (N - 1 + mo) % mo * two[g] % mo) % mo, N) % mo;
ans %= mo;
ll lst = (two[t] + (N - 1 + mo) % mo * two[g] % mo) % mo;
ll l = 0;
for (int i = 1; i <= m; i++) l = ((l << 1) + n[i] - '0') % mo;
ll r = (lst + two[g] - 1 + mo) % mo;
ans -= (r - l + mo) % mo * lst % mo;
ans = (ans % mo + mo) % mo;
printf("%lld
", ans);
}
return 0;
}