提出 #67006318
ソースコード 拡げる
#include <bits/stdc++.h>
#define ll long long
#define N 2000010
using namespace std;
ll read(){
char cc;
while(1){cc=getchar();if((cc>='0'&&cc<='9')||cc=='-')break;}
ll sum=0,flag=1;
cc=='-'?flag=-1:sum=(cc^48);
while(1){cc=getchar();if(!(cc>='0'&&cc<='9'))break;sum=(sum<<1)+(sum<<3)+(cc^48);}
return sum*flag;
}
void write(ll x){
if(!x)putchar('0');
if(x<0){x=-x;putchar('-');}
ll cc[25],cntt=0;
while(x){cc[++cntt]=x%10;x/=10;}
for(ll i=cntt;i>=1;i--)putchar(cc[i]+'0');
putchar('\n');
}
const ll mod=998244353;
ll n,cnt=1,t[N][2],f[N],s[N],shu2[N],fa[N],a[N];
char c[N];
int main(){
shu2[0]=1;
for(ll i=1;i<=500000;i++)shu2[i]=shu2[i-1]*2%mod;
n=read();
for(ll tt=1;tt<=n;tt++){
scanf("%s",c+1);
ll p=1;
ll m=strlen(c+1);
for(ll i=1;i<=m;i++){
ll z=(c[i]=='A'?0:1);
if(!t[p][z]){
t[p][z]=++cnt;
fa[cnt]=p;
}
p=t[p][z];
}
a[p]++;
while(p){
s[p]=s[t[p][0]]+s[t[p][1]]+a[p];
f[p]=f[t[p][0]]*f[t[p][1]]%mod;
if(a[p]){
f[p]=(f[p]+shu2[s[p]-a[p]]*(mod-1+shu2[a[p]])%mod)%mod;
}
p=fa[p];
}
write(f[1]);
}
return 0;
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | C - Prefix Covering |
| ユーザ | yixiuge777 |
| 言語 | C++ 20 (gcc 12.2) |
| 得点 | 600 |
| コード長 | 1147 Byte |
| 結果 | AC |
| 実行時間 | 21 ms |
| メモリ | 29932 KiB |
コンパイルエラー
Main.cpp: In function ‘int main()’:
Main.cpp:31:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
31 | scanf("%s",c+1);
| ~~~~~^~~~~~~~~~
ジャッジ結果
| セット名 | Sample | All | ||||
|---|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 0 | 600 / 600 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| Sample | sample-01.txt, sample-02.txt |
| All | 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 05-01.txt, 05-02.txt, 05-03.txt, 05-04.txt, 05-05.txt, 05-06.txt, 05-07.txt, 05-08.txt, 06-01.txt, 06-02.txt, 06-03.txt, 06-04.txt, 06-05.txt, 06-06.txt, 06-07.txt, 06-08.txt, 07-01.txt, 07-02.txt, 07-03.txt, 07-04.txt, 07-05.txt, 08-01.txt, 08-02.txt, 08-03.txt, 08-04.txt, 09-01.txt, 09-02.txt, 09-03.txt, 09-04.txt, sample-01.txt, sample-02.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| 02-01.txt | AC | 4 ms | 7580 KiB |
| 02-02.txt | AC | 4 ms | 7560 KiB |
| 02-03.txt | AC | 4 ms | 7496 KiB |
| 02-04.txt | AC | 4 ms | 7560 KiB |
| 02-05.txt | AC | 4 ms | 7620 KiB |
| 02-06.txt | AC | 4 ms | 7436 KiB |
| 02-07.txt | AC | 5 ms | 7568 KiB |
| 02-08.txt | AC | 4 ms | 7648 KiB |
| 02-09.txt | AC | 4 ms | 7616 KiB |
| 02-10.txt | AC | 5 ms | 7524 KiB |
| 02-11.txt | AC | 5 ms | 7748 KiB |
| 02-12.txt | AC | 6 ms | 8000 KiB |
| 02-13.txt | AC | 9 ms | 8336 KiB |
| 02-14.txt | AC | 13 ms | 9216 KiB |
| 03-01.txt | AC | 5 ms | 7792 KiB |
| 03-02.txt | AC | 5 ms | 7824 KiB |
| 03-03.txt | AC | 6 ms | 8004 KiB |
| 03-04.txt | AC | 9 ms | 8276 KiB |
| 03-05.txt | AC | 15 ms | 9076 KiB |
| 04-01.txt | AC | 17 ms | 27640 KiB |
| 04-02.txt | AC | 17 ms | 27456 KiB |
| 04-03.txt | AC | 17 ms | 27152 KiB |
| 04-04.txt | AC | 17 ms | 27192 KiB |
| 05-01.txt | AC | 17 ms | 10024 KiB |
| 05-02.txt | AC | 18 ms | 10624 KiB |
| 05-03.txt | AC | 18 ms | 10940 KiB |
| 05-04.txt | AC | 19 ms | 11432 KiB |
| 05-05.txt | AC | 18 ms | 11984 KiB |
| 05-06.txt | AC | 21 ms | 21104 KiB |
| 05-07.txt | AC | 21 ms | 25900 KiB |
| 05-08.txt | AC | 20 ms | 29752 KiB |
| 06-01.txt | AC | 17 ms | 9984 KiB |
| 06-02.txt | AC | 18 ms | 10372 KiB |
| 06-03.txt | AC | 18 ms | 10892 KiB |
| 06-04.txt | AC | 18 ms | 11408 KiB |
| 06-05.txt | AC | 18 ms | 11904 KiB |
| 06-06.txt | AC | 20 ms | 21204 KiB |
| 06-07.txt | AC | 20 ms | 25808 KiB |
| 06-08.txt | AC | 19 ms | 29932 KiB |
| 07-01.txt | AC | 14 ms | 10116 KiB |
| 07-02.txt | AC | 14 ms | 10052 KiB |
| 07-03.txt | AC | 13 ms | 9804 KiB |
| 07-04.txt | AC | 13 ms | 9980 KiB |
| 07-05.txt | AC | 14 ms | 10104 KiB |
| 08-01.txt | AC | 15 ms | 10016 KiB |
| 08-02.txt | AC | 14 ms | 9928 KiB |
| 08-03.txt | AC | 14 ms | 9940 KiB |
| 08-04.txt | AC | 14 ms | 10016 KiB |
| 09-01.txt | AC | 14 ms | 9984 KiB |
| 09-02.txt | AC | 14 ms | 9892 KiB |
| 09-03.txt | AC | 14 ms | 9976 KiB |
| 09-04.txt | AC | 14 ms | 9944 KiB |
| sample-01.txt | AC | 4 ms | 7520 KiB |
| sample-02.txt | AC | 4 ms | 7548 KiB |