Submission #17682373

---

Source Code Expand

#include<bits/stdc++.h>
typedef int LL;
typedef double dl;
#define opt operator
#define pb push_back
const LL maxn=7e3+9,mod=998244353,inf=0x3f3f3f3f;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
void Chkmin(LL &x,LL y){
	if(y<x) x=y;
}
void Chkmax(LL &x,LL y){
	if(y>x) x=y;
}
LL add(LL x,LL y){
	return x+=y,x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	return x-=y,x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1); while(b){
		if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
	}return ret;
}
LL n,ans;
LL B[maxn][maxn],vis[maxn],a[maxn],fc2[maxn],b[maxn];
char s[maxn][maxn];
void Insert(LL *A,LL len){
	for(LL i=len;i>=1;--i)if(A[i]){
		if(!vis[i]){
			for(LL j=1;j<=i;++j) B[i][j]=A[j]; vis[i]=1;
			return;
		}else{
			for(LL j=1;j<=i;++j) A[j]^=B[i][j];
		}
	}
}
void Solve(){
	LL cnt(0);
	for(LL i=strlen(s[0]+1);i>=1;--i) cnt+=vis[i];
	if(!vis[strlen(s[0]+1)]){
		printf("%d\n",fc2[cnt]); return;
	}
	static LL C[maxn];
	/*
	for(LL i=strlen(s[0]+1);i>=1;--i){
		for(LL j=1;j<=i;++j) printf("%d",B[i][j]); puts("");
	}
	*/
	//printf("# %d\n",cnt);
	//for(LL i=strlen(s[0]+1);i>=1;--i) printf("%d",a[i]); puts("");
	for(LL i=strlen(s[0]+1);i>=1;--i) 
	    if(vis[i]){
		    --cnt;
		    if(a[i]){
		    	if(C[i]){
		    		ans=add(ans,fc2[cnt]);
				}else{
					//puts("033");
					ans=add(ans,fc2[cnt]);
					for(LL j=1;j<=i;++j) C[j]^=B[i][j];
				}
			}else{
				if(C[i]){
					for(LL j=1;j<=i;++j) C[j]^=B[i][j];
				}
			}
			//printf("(%d,%d)\n",i,ans);
	    }else{
	    	if(!a[i] && C[i]){
	    		printf("%d\n",ans); 
				return;
			}
	    	if(a[i] && !C[i]){
	    		ans=add(ans,fc2[cnt]); printf("%d\n",ans);
	    		return;
			}
		}
	ans=add(ans,1);
	printf("%d\n",ans);
}
int main(){
	n=Read(); scanf(" %s",s[0]+1);
	for(LL i=1,len=strlen(s[0]+1);i<=len;++i) a[i]=s[0][i]-'0';
	for(LL i=1,len=strlen(s[0]+1);i<=len/2;++i) std::swap(a[i],a[len-i+1]);
	//for(LL i=strlen(s[0]+1);i>=1;--i) printf("%d",a[i]); puts("");
	LL mx=(strlen(s[0]+1));
	fc2[0]=1; for(LL i=1;i<=mx;++i) fc2[i]=mul(fc2[i-1],2);
	mx+=3000;
	for(LL i=1;i<=n;++i){
		scanf(" %s",s[i]+1);
		Chkmax(mx,strlen(s[i]+1));
		LL len(strlen(s[i]+1));
		for(LL j=1;j<=(len/2);++j) std::swap(s[i][j],s[i][len-j+1]);
	}
	//for(LL i=1;i<=n;++i) printf("%s\n",s[i]+1);
	//printf("%d\n",mx);
	for(LL i=1;i<=n;++i){
		LL len(strlen(s[i]+1));
		for(LL j=1;j<=len;++j) b[j]=s[i][j]-'0';
		while(len<=mx){
			Insert(b,len);
			++len;
			for(LL j=len;j>=1;--j) b[j]=b[j-1];
		}
	}
	Solve();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘LL Read()’:
./Main.cpp:10:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   10 |   if(c=='-') f=-1; c=getchar();
      |   ^~
./Main.cpp:10:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   10 |   if(c=='-') f=-1; c=getchar();
      |                    ^
./Main.cpp: In function ‘LL Pow(LL, LL)’:
./Main.cpp:33:3: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   33 |   if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
      |   ^~
./Main.cpp:33:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   33 |   if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;
      |                              ^~~~
./Main.cpp: In function ‘void Insert(LL*, LL)’:
./Main.cpp:42:4: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   42 |    for(LL j=1;j<=i;++j) B[i][j]=A[j]; vis[i]=1;
      |    ^~~
./Main.cpp:42:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   42 |    for(LL j=1;j<=i;++j) B[i][j]=A[j]; vis[i]=1;
      |                                       ^~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:94:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   94 |  n=Read(); scanf(" %s",s[0]+1);
      |            ~~~~~^~~~~~~~~~~~~~
./Main.cpp:102:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  102 |   scanf(" %s",s[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~

Judge Result