QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#381739#3082. Ascending MatrixxlwangWA 0ms11788kbC++143.2kb2024-04-07 20:41:372024-04-07 20:41:38

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 20:41:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11788kb
  • [2024-04-07 20:41:37]
  • 提交

answer

#include<bits/stdc++.h>
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
using namespace std;
inline int read(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)) f|=(c=='-'),c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
//	int t=read();
//	while(t--) work();
//}
const int Maxn=25,Maxm=(1<<23)+10,mod=998244353;
int stk[Maxm],top;
char c[Maxn];
int id[Maxm];
int f[Maxm],s[Maxm];
inline int ksm(int x,int y=mod-2){
    int sum=1;
    while(y){
        if(y&1) sum=1ll*sum*x%mod;
        y=y/2;x=1ll*x*x%mod;
    }
    return sum;
}
inline void add(int &x,int y){
    x+=y;if(x>=mod) x-=mod;
}
int n,N;
int p,_p;
int a,b;
inline void init(){
    scanf("%s",c+1);n=strlen(c+1);
    N=(1<<n)-1;
    int x,y;
    x=read();y=read();a=x;b=y;
    p=1ll*x*ksm((x+y)%mod)%mod;_p=(1-p+mod)%mod;
}
int st;
int to[Maxm];
inline int getsum(int l,int r){
    if(l>r) return 0;
    return (s[l]-s[r+1]+mod)%mod;
}
inline void work(){
    fr(i,1,n) st+=(1<<(i-1))*(c[i]=='1');
    int tp=st;
    if(tp==(1<<n)-1){
        puts("0");
        return;
    }
    if(a==0){
        puts("-1");
        return;
    }
    if(b==0){
        if(tp==0){
            writeln(n);
            return;
        }
        int now=0;
        fr(i,1,n-1) if(c[i]!=c[i+1]){
            if(now){
                puts("-1");
                return;
            }
            now=i-1;
        }
        // cout<<now<<endl;
        if(c[now]=='0') writeln(now+1);
        else if(!now) writeln(n+1);
        else writeln(-1);
        return;
    }
    queue<int> q;q.push(N);
    int NUM=0;
    fr(i,1,n-1) NUM+=(1<<(i-1));
    fr(i,0,N){
        int x=q.front();q.pop();
        int a,b;a=((x)&NUM)*2;b=a+1;
        // cout<<x<<' '<<a<<' '<<b<<endl;
        id[x]=i;to[i]=x;
        if(!id[a]) q.push(a);
        else q.push(b);
    }
    // fr(i,0,N) cout<<to[i]<<' ';cout<<endl;
    // cout<<p<<' '<<_p<<endl;
    int A,B;
    A=1ll*b*ksm(a)%mod;B=1ll*a*ksm(b)%mod;
    // cout<<A<<' '<<B<<endl;
    rf(i,N,1){
        int x=to[i];
        if((x&1)) f[i]=1;
        else {
            int a,b;a=(x/2);b=a+(1<<(n-1));a=id[a];b=id[b];
            // cout<<"*"<<i<<' '<<x<<' '<<A<<' '<<B<<endl;
            if(a==i-1) f[i]=(1+1ll*B*(getsum(i+1,b)+1)%mod)%mod;
            else f[i]=(1+1ll*A*(getsum(i+1,a)+1)%mod)%mod;
        }
        s[i]=(s[i+1]+f[i])%mod;
    }
    // fr(i,0,N) cout<<i<<' '<<f[i]<<endl;
    writeln(getsum(1,id[st]));
}
signed main(){
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
    init();work();
    // printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 11788kb

input:

148 129 48 144 105 13

output:

626603721

result:

wrong answer 1st lines differ - expected: '467058311', found: '626603721'