QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#381739 | #3082. Ascending Matrix | xlwang | WA | 0ms | 11788kb | C++14 | 3.2kb | 2024-04-07 20:41:37 | 2024-04-07 20:41:38 |
Judging History
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;
}
详细
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'