Atcoder Regular Contst 084 D - XorShift（bitset）

没错，这就是 Small Multiple 那场的 F，显然这种思维题对我来说都是不可做题/cg/cg/cg

首先如果我们把每个二进制数看作一个模 \(2\) 意义下的多项式 \(F(x)=\sum\limits_{i=0}^na_ix^i(a_i\in\{0,1\})\)，那么上述操作就可以看作给一个多项式乘 \(x\) 和两个多项式加（减），我们记 \(D\) 为所有多项式的 \(\gcd\)，或者更严谨一点，对于两个多项式 \(P(x),Q(x)\)，我们定义 \(\gcd(P,Q)\) 为：

如果 \(Q=0\)，那么 \(\gcd(P,Q)=P\)
否则不妨假设 \(\deg P\ge\deg Q\)，那么 \(\gcd(P,Q)=\gcd(Q,P-Q\times x^{\deg P-\deg Q})\)

通过上面辗转相除的过程我们就能够从两个多项式 \(P,Q\) 得到它们的 \(\gcd(P,Q)\)。而显然对于一个多项式 \(F\)，它的任意倍都是可以被表示出来的，具体来说就是不断给它乘 \(x\)，然后把你要乘的那个倍数中为 \(1\) 的位加在一起。又因为任意时刻黑板上所有多项式都是 \(D\) 的倍数，因此我们可以得到结论：

Observation \(1\). 有且只有 \(D\) 的倍数能够被表示出来

也就是说我们的问题转化为要求有多少个多项式 \(P\) 满足：

\(P\) 是 \(D\) 的倍数，也就是说 \(\exists Q,s.t. DQ=P\)
\(P\) 在二进制表示下 \(\le X\)

考虑怎么求这个东西，我们按照字典序的套路枚举一个 \(l\) 满足 \(P\) 与 \(X\) 最高位到第 \(l+1\) 低的位均相同，且 \(P\) 第 \(l\) 低的位严格小于 \(X\) 第 \(l\) 低的位，但是这个东西还是一脸不好求的样子。不过别急，我们不妨再来找些性质：

Observation \(2\). 对于一个二进制数 \(T\)，如果 \(T\) 从第 \(\deg D\) 到其最高位都已确定，那么存在唯一的确定后 \(\deg D\) 位的方式使其成为 \(D\) 的倍数

具体方法就是设将 \(T\) 后 \(\deg D\) 位全填上 \(0\) 得到的二进制数为 \(T_0\)，那么我们就在 \(T\) 后 \(\deg D\) 位上填上 \(T_0\bmod D\)，正确性显然。

有了这个性质之后此题就变得很可做了。如果 \(l\ge\deg D\)，那么有 \(l-\deg D\) 位可以随便填，方案数为 \(2^{l-\deg D}\)，否则 \(P\) 的 \(\deg D\) 位到最高位已经唯一确定了，因此我们就能唯一确定 \(P\) 的每一位取值，多项式取个模把它补全后与 \(X\) 比个大小即可。

时间复杂度 \(\mathcal O(n|a_i|^2)\)，不过由于此题每一位取值只有 \(0/1\) 两种，因此我们可以很自然地想到 bitset 优化，这样取模和求 \(\text{gcd}\) 的复杂度均可降到 \(\mathcal O(\dfrac{|a_i|^2}{\omega})\)，总复杂度就变成了 \(\mathcal O(\dfrac{n|a_i|^2}{\omega})\)

const int MAXN=4e3;

const int MOD=998244353;

struct poly{

	bitset<MAXN+5> bs;int m;

	void clear(){while(m&&!bs.test(m)) --m;}

};

poly getgcd(poly x,poly y){

	while(x.bs.any()&&y.bs.any()){

		if(x.m>=y.m) x.bs^=y.bs<<(x.m-y.m),x.clear();

		else y.bs^=x.bs<<(y.m-x.m),y.clear();

	} return (x.bs.any())?x:y;

}

poly getmod(poly x,poly y){

	while(x.m>=y.m){

		x.bs^=y.bs<<(x.m-y.m);

		x.clear();

	} return x;

}

poly d,tmp;int n,len,pw2[MAXN+5];

char m[MAXN+5],buf[MAXN+5];

int main(){

	scanf("%d%s",&n,m+1);len=strlen(m+1);

	for(int i=(pw2[0]=1);i<=len;i++) pw2[i]=pw2[i-1]*2%MOD;

	for(int i=1;i<=n;i++){

		scanf("%s",buf+1);int l=strlen(buf+1);tmp.bs.reset();tmp.m=l;

		for(int j=1;j<=l;j++) if(buf[j]^48) tmp.bs.set(l-j+1);d=getgcd(d,tmp);

	} if(len<d.m) return puts("1"),0;int ans=0;

	for(int i=1;i<=len-d.m+1;i++) if(m[i]^48) ans=(ans+pw2[len-d.m+1-i])%MOD;

	tmp.m=len;tmp.bs.reset();for(int i=1;i<=len-d.m+1;i++) if(m[i]^48) tmp.bs.set(len-i+1);

	tmp=getmod(tmp,d);int add=1;

	for(int i=d.m-1;i;i--){

		if(tmp.bs.test(i)<(m[len-i+1]^48)){add=1;break;}

		if(tmp.bs.test(i)>(m[len-i+1]^48)){add=0;break;}

	} (ans+=add)%=MOD;printf("%d\n",ans);

	return 0;

}

巴特西

Atcoder Regular Contst 084 D - XorShift（bitset）

最新文章

热门文章