牛客 OI 赛前集训营-提高组（第一场）C - 与巨——二进制、结论

进不去的题面题目描述

题解

首先可以发现， G ( i ) G(i) G(i) 的二进制最高位以前全是1，而且最高位和 i i i 相同，所以 [ ( i ∗ c ) & G ( i ) = i ] [(i*c)&G(i)=i] [(i∗c)&G(i)=i] 相当于 i i i 乘以 c c c 过后，原来的数位上不变。

考虑什么情况下原来的数位不会变。如果 c c c 是偶数，那么 i ∗ c i*c i∗c 和 i i i 的最低位必定不相同，所以答案为0。如果 c c c 是1，那么显然每个数都符合要求。

如果 c c c 是不为1的奇数？考虑 c c c 的二进制表示的最后两个1：一个是1，一个是 g = l o w b i t ( c − 1 ) g=rm lowbit(c-1) g=lowbit(c−1)。

...001000001  c
       10111  i
     1011010  i
    10101100  i
	...

若 i < g i 若 i i i 的最高位和 g g g 相同，此时 i i i 的最后一位必须为0，否则在最高位以前必定和原数不同；
若 i i i 的最高位比 g g g 大一位，此时 i i i 的最后两位必须为0，否则在最高位以前必定和原数不同；
以此类推。

于是可以得到结论：假设 g = 2 w g=2^w g=2w，那么符合条件的 i i i 必须满足二进制只有最高的 w w w 位以内存在1，其它位上必须全为0。由于 d p c , i dp_{c,i} dpc,i 是求前缀最大值，所以 d p c , i dp_{c,i} dpc,i 就等于 i i i 保留最高的 w w w 位的结果。

知道了结论过后，我们只需要设计一下怎么在 O ( ∣ n ∣ ) O(|n|) O(∣n∣) 复杂度以内统计答案即可。

c c c 为偶数直接输出0， c c c 为1则直接用公式计算 0 ∼ n 0sim n 0∼n 的等差数列求和即可。

对于其它情况，我们可以枚举数的最高位 i i i，如果位数 i < ∣ n ∣ i<|n| i<∣n∣，那么前 w w w 位的每一种值都要被计算 2 i − w 2^{i-w} 2i−w 次，所以只需要用等差数列求和计算一下前 w w w 位的值的和。

如果位数 i = ∣ n ∣ i=|n| i=∣n∣，那么在前 w w w 位没取到最大时，仍然每一种都会被计算 2 ∣ n ∣ − w 2^{|n|-w} 2∣n∣−w 次，而前 w w w 位的最大值会被计算 ( n m o d 2 ∣ n ∣ − w ) + 1 (nmod 2^{|n|-w})+1 (nmod2∣n∣−w)+1（ n n n 的后 ∣ n ∣ − w |n|-w ∣n∣−w 位的值+1）次，再次用等差数列求和计算即可。

代码

#include//JZM yyds!!
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define uns unsigned
#define MOD 998244353ll
#define MAXN 10000005
#define INF 1e18
#define lowbit(x) ((x)&(-(x)))
#define IF it->first
#define IS it->second
using namespace std;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0)f^=(s=='-'),s=getchar();
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
inline ll ksm(ll a,ll b,ll mo){
	ll res=1;
	for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;
	return res;
}
const ll iv2=((MOD+1)>>1);
char s[MAXN];
int n;
ll c,mi[MAXN];
inline int AD(int a,int b){
	a+=b;return a>=MOD?a-MOD:a;
}
inline void init(int n){
	mi[0]=1;
	for(int i=1;i<=n;i++)mi[i]=AD(mi[i-1],mi[i-1]);
}
signed main()
{
	init(10000000);
	for(int T=read();T--;){
		scanf("%s",s+1),n=strlen(s+1);
		c=read();
		if(~c&1){
			printf("0n");
			continue;
		}
		if(c==1){
			ll f=0;
			for(int i=1;i<=n;i++)f=((f<<1)+(s[i]^48))%MOD;
			printf("%lldn",f*(f+1)%MOD*iv2%MOD);
			continue;
		}
		ll ans=0;
		ll g=lowbit(c^1);
		int w=0;
		while((1ll<1;i--,j++){
			int e=min(w-1,j);
			ll p=1ll<

牛客 OI 赛前集训营-提高组（第一场）C - 与巨——二进制、结论

C/C++/C#相关栏目本月热门文章