QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100042 | #6344. The Best Problem of 2021 | aurelion_sol | WA | 2ms | 3676kb | C++14 | 3.4kb | 2023-04-24 15:03:32 | 2023-04-24 15:03:37 |
Judging History
answer
#include<bits/stdc++.h>
#define rp(i,a,b) for(int i=a;i<=b;++i)
#define pr(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
//xiaoyaowudi
constexpr int N(2010),p(998244353);
int n,x[N];
void init(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int m,cnt(0);
std::cin>>n>>m;
static bool hv[N];
static std::bitset<N> b[N];
static std::bitset<N> a[N],xb;
for(int i(1);i<=n;++i)
{
static char s[N];std::cin>>s;
for(int j(0);j<m;++j)
{
a[i][m-j-1]=(s[j]=='1');
}
bool st(false);
for(int j(m-1);j>=0;--j) if(a[i][j])
{
if(hv[j])
{
a[i]^=b[j];
}
else
{
hv[j]=st=true;
b[j]=a[i];
break;
}
}
if(!st){std::cout<<0<<std::endl;exit(0);}
}
{
static char s[N];std::cin>>s;
for(int j(0);j<m;++j) xb[m-j-1]=(s[j]=='1');
}
for(int i(m-1);i>=0;--i) if(hv[i]) for(int j(i+1);j<m;++j) if(hv[j] && b[j][i]) b[j]^=b[i];
static std::bitset<N> cur;
for(int j(m-1);j>=0;--j) if(hv[j])
{
std::bitset<N> nw(cur^b[j]);
bool cap(true);
for(int t(m-1);t>=0;--t) if(xb[t]!=nw[t])
{
if(xb[t]<nw[t]) cap=false;
break;
}
if(cap) cur=nw,x[++cnt]=1;
else x[++cnt]=0;
}
if(!x[1]){std::cout<<0<<std::endl;exit(0);}
}
//~xiaoyaowudi
typedef long long ll;
constexpr int q(p-1);
inline int inc(int x,int y){
return x+=y-p,x+=x>>31&p;
}
inline int dec(int x,int y){
return x-=y,x+=x>>31&p;
}
inline int mul(int x,int y){
return ll(x)*y%p;
}
inline void upd(int&x,int y){
x=inc(x,y);
}
int ksm(int x,int y){
int z=1;
for(;y;y>>=1,x=mul(x,x))if(y&1)z=mul(x,z);
return z;
}
int ksm_e(int x,int y){
int z=1;
for(;y;y>>=1,x=ll(x)*x%q)if(y&1)z=ll(x)*z%q;
return z;
}
int v[N],w[N],iw[N],wx[N][2],a2[N],i2[N],h[N][N],g[N][N][2],f[N][N][4],a[N],b[N],c[N];
void init_val(){
rp(i,0,n){
v[i]=ksm(2,ksm_e(2,i));
w[i]=ksm(2,i);
iw[i]=ksm(w[i],p-2);
wx[i][0]=w[i];
wx[i][1]=0;
}
a2[0]=1;
rp(i,1,n){
a2[i]=mul(a2[i-1],w[i]-1);
}
i2[n]=ksm(a2[n],p-2);
pr(i,n,1){
i2[i-1]=mul(i2[i],w[i]-1);
}
}
int main(){
freopen("1.in","r",stdin);
init();
init_val();
/*
rp(i,1,n){
printf("%d",x[i]);
}
puts("");
*/
h[n+1][0]=1;
pr(i,n,2){
rp(j,0,n-i){
int u=mul(v[j],w[n-i-j]);
h[i][j]=inc(h[i][j],h[i+1][j]);
h[i][j+1]=inc(h[i][j+1],mul(u,h[i+1][j]));
}
}
g[n+1][0][0]=1;
g[n+1][0][1]=1;
pr(i,n,2){
rp(j,0,n-i){
rp(k,0,1){
int t=mul(w[n-i-j],k&&!x[i]?1:v[j]);
upd(g[i][j][k],g[i+1][j][k]);
upd(g[i][j+1][k],mul(t,g[i+1][j][k]));
}
}
if(x[i]){
rp(j,0,n-i){
upd(g[i][j][1],mul(w[n-i-j],g[i+1][j][0]));
}
}
}
f[n+1][0][0]=1;
f[n+1][0][1]=1;
pr(i,n,2){
rp(j,0,n-i){
rp(k,0,3){
int u=mul(w[n-i-j],k==3&&!x[i]?1:v[j]);
upd(f[i][j][k],f[i+1][j][k]);
if(!k||k==3||!x[i]){
upd(f[i][j+1][k],mul(u,f[i+1][j][k]));
}
}
if(x[i]){
upd(f[i][j+1][1],f[i+1][j][0]);
upd(f[i][j+1][3],mul(w[n-i-j],f[i][j][2]));
}else{
upd(f[i][j][2],mul(w[n-i-j],f[i+1][j][1]));
}
}
}
a[0]=a2[n];
rp(j,1,n){
int x=inc(h[2][j],mul(v[j-1],g[2][j-1][1]));
int y=inc(f[2][j-1][2],mul(v[j-1],f[2][j-1][3]));
// printf("%d:%d %d\n",j,x,y);
a[j]=mul(inc(x,y),a2[n-j]);
}
rp(i,0,n){
int u=mul(i2[i],ksm(2,i*(i-1)/2));
b[i]=i&1?p-u:u;
}
rp(i,0,n){
rp(j,0,i){
c[i]=inc(c[i],mul(b[j],a[i-j]));
}
}
printf("%d\n",c[n]);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3676kb
input:
4 4 0001 0010 0100 1000 1101
output:
0
result:
wrong answer 1st numbers differ - expected: '7364', found: '0'