結果
| 問題 |
No.1646 Avoid Palindrome
|
| コンテスト | |
| ユーザー |
 tails
|
| 提出日時 | 2021-08-16 19:57:02 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 65 ms / 3,000 ms |
| コード長 | 5,120 bytes |
| コンパイル時間 | 1,205 ms |
| コンパイル使用メモリ | 36,608 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-08 16:20:53 |
| 合計ジャッジ時間 | 4,365 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 40 |
コンパイルメッセージ
main.c: In function 'm_zero':
main.c:30:9: warning: implicit declaration of function 'memset' [-Wimplicit-function-declaration]
30 | memset(&r,0,sizeof r);
| ^~~~~~
main.c:1:1: note: include '<string.h>' or provide a declaration of 'memset'
+++ |+#include <string.h>
1 | #pragma GCC optimize("Ofast")
main.c:30:9: warning: incompatible implicit declaration of built-in function 'memset' [-Wbuiltin-declaration-mismatch]
30 | memset(&r,0,sizeof r);
| ^~~~~~
main.c:30:9: note: include '<string.h>' or provide a declaration of 'memset'
main.c: At top level:
main.c:145:1: warning: return type defaults to 'int' [-Wimplicit-int]
145 | main(){
| ^~~~
main.c: In function 'main':
main.c:150:25: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration]
150 | write(1,"26",2);
| ^~~~~
main.c:154:17: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration]
154 | _exit(0);
| ^~~~~
| _Exit
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
char*mmap();
#define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}
#define wt(v) {long _z=v;do*--wp=_z%10+48;while(_z/=10);}
#define rep(v,e) for(long v=0;v<e;++v)
#define MD 998244353
typedef long D[26][26];
D d1,d2;
void nextd(){
for(int j=0;j<26;++j){
for(int i=0;i<26;++i){
d1[j][i]=d2[j][i]%MD;
d2[j][i]=0;
}
}
}
typedef struct {
long v[2][2][2][2]; // [i==a][i==b][j==a][j==b]
} M;
static M m_zero(){
M r;
memset(&r,0,sizeof r);
return r;
}
static M m_mul(M a,M b){
M r=m_zero();
r.v[0][0][0][0]=(((
a.v[0][0][0][0]*b.v[0][0][0][0]+
0)%MD*21+
a.v[0][0][0][0]*b.v[0][0][0][1]+
a.v[0][0][0][0]*b.v[0][0][1][0]+
a.v[0][0][0][0]*b.v[0][1][0][0]+
a.v[0][0][0][0]*b.v[1][0][0][0]+
a.v[0][0][0][1]*b.v[0][0][0][0]+
a.v[0][0][1][0]*b.v[0][0][0][0]+
a.v[0][1][0][0]*b.v[0][0][0][0]+
a.v[1][0][0][0]*b.v[0][0][0][0]+
0)%MD*22+
a.v[0][0][0][0]*b.v[0][1][1][0]+
a.v[0][0][0][0]*b.v[1][0][0][1]+
a.v[0][0][0][1]*b.v[0][0][1][0]+
a.v[0][0][0][1]*b.v[1][0][0][0]+
a.v[0][0][1][0]*b.v[0][0][1][0]+
a.v[0][0][1][0]*b.v[1][0][0][0]+
a.v[0][1][0][0]*b.v[0][0][0][1]+
a.v[0][1][0][0]*b.v[0][1][0][0]+
a.v[0][1][1][0]*b.v[0][0][0][0]+
a.v[1][0][0][0]*b.v[0][0][0][1]+
a.v[1][0][0][0]*b.v[0][1][0][0]+
a.v[1][0][0][1]*b.v[0][0][0][0]+
0)%MD;
r.v[0][0][0][1]=(((
a.v[0][0][0][0]*b.v[0][0][0][0]+
0)%MD*22+
a.v[0][0][0][0]*b.v[0][1][0][0]+
a.v[0][0][0][0]*b.v[1][0][0][0]+
a.v[0][0][0][1]*b.v[0][0][0][1]+
a.v[0][0][1][0]*b.v[0][0][0][0]+
a.v[0][1][0][0]*b.v[0][0][1][0]+
a.v[1][0][0][0]*b.v[0][0][0][0]+
0)%MD*23+
a.v[0][0][0][1]*b.v[1][0][0][1]+
a.v[0][0][1][0]*b.v[1][0][0][0]+
a.v[0][1][0][0]*b.v[0][1][1][0]+
a.v[0][1][1][0]*b.v[0][0][1][0]+
a.v[1][0][0][0]*b.v[0][1][0][0]+
a.v[1][0][0][1]*b.v[0][0][0][1]+
0)%MD;
r.v[0][0][1][0]=(((
a.v[0][0][0][0]*b.v[0][0][0][0]+
0)%MD*22+
a.v[0][0][0][0]*b.v[0][1][0][0]+
a.v[0][0][0][0]*b.v[1][0][0][0]+
a.v[0][0][0][1]*b.v[0][0][0][0]+
a.v[0][0][1][0]*b.v[0][0][0][1]+
a.v[0][1][0][0]*b.v[0][0][0][0]+
a.v[1][0][0][0]*b.v[0][0][1][0]+
0)%MD*23+
a.v[0][0][0][1]*b.v[1][0][0][0]+
a.v[0][0][1][0]*b.v[1][0][0][1]+
a.v[0][1][0][0]*b.v[0][1][0][0]+
a.v[0][1][1][0]*b.v[0][0][0][1]+
a.v[1][0][0][0]*b.v[0][1][1][0]+
a.v[1][0][0][1]*b.v[0][0][1][0]+
0)%MD;
r.v[0][1][0][0]=(((
a.v[0][0][0][0]*b.v[0][0][0][0]+
0)%MD*22+
a.v[0][0][0][0]*b.v[0][0][0][1]+
a.v[0][0][0][0]*b.v[0][0][1][0]+
a.v[0][0][0][1]*b.v[0][1][0][0]+
a.v[0][0][1][0]*b.v[0][0][0][0]+
a.v[0][1][0][0]*b.v[1][0][0][0]+
a.v[1][0][0][0]*b.v[0][0][0][0]+
0)%MD*23+
a.v[0][0][0][1]*b.v[0][1][1][0]+
a.v[0][0][1][0]*b.v[0][0][1][0]+
a.v[0][1][0][0]*b.v[1][0][0][1]+
a.v[0][1][1][0]*b.v[1][0][0][0]+
a.v[1][0][0][0]*b.v[0][0][0][1]+
a.v[1][0][0][1]*b.v[0][1][0][0]+
0)%MD;
r.v[0][1][1][0]=(((
a.v[0][0][0][0]*b.v[0][0][0][0]+
0)%MD*23+
a.v[0][0][0][1]*b.v[0][1][0][0]+
a.v[0][0][1][0]*b.v[0][0][0][1]+
a.v[0][1][0][0]*b.v[1][0][0][0]+
a.v[1][0][0][0]*b.v[0][0][1][0]+
0)%MD*24+
a.v[0][1][1][0]*b.v[1][0][0][1]+
a.v[1][0][0][1]*b.v[0][1][1][0]+
0)%MD;
r.v[1][0][0][0]=r.v[0][0][0][1];
r.v[1][0][0][1]=(((
a.v[0][0][0][0]*b.v[0][0][0][0]+
0)%MD*23+
a.v[0][0][0][1]*b.v[0][0][0][1]+
a.v[0][0][1][0]*b.v[0][1][0][0]+
a.v[0][1][0][0]*b.v[0][0][1][0]+
a.v[1][0][0][0]*b.v[1][0][0][0]+
0)%MD*24+
a.v[0][1][1][0]*b.v[0][1][1][0]+
a.v[1][0][0][1]*b.v[1][0][0][1]+
0)%MD;
return r;
}
main(){
char*rp=mmap(0l,1l<<25,1,2,0,0ll);
rd(n);
if(n==1){
if(*rp=='?'){
write(1,"26",2);
}else{
write(1,"1",1);
}
_exit(0);
}
{
long c0=*rp++;
long c1=*rp++;
rep(i,26){
rep(j,26){
d1[i][j]=(c0=='?'|c0-'a'==i)&(c1=='?'|c1-'a'==j)&(i!=j);
}
}
}
while(1){
char*rp0=rp;
while(*rp=='?'){
++rp;
}
long l=rp-rp0;
if(l>=1<<10){
M e=m_zero();
e.v[0][1][0][0]=1;
M m=e;
for(--l;l;l>>=1){
if(l&1){
m=m_mul(m,e);
}
e=m_mul(e,e);
}
rep(i,26){
rep(j,26){
if(i!=j){
rep(a,26){
rep(b,26){
d2[i][j]+=m.v[i==a][i==b][j==a][j==b]*d1[a][b]%MD;
}
}
}
}
}
nextd();
}else{
for(;--l>=0;){
rep(i,26){
long s=0;
rep(j,26){
s+=d1[j][i];
}
rep(j,26){
d2[i][j]=i==j?0:s-d1[j][i];
}
}
nextd();
}
}
long c1=*rp++-'a';
if(c1<0){
break;
}
long d3[26];
rep(i,26){
d3[i]=-d1[c1][i];
rep(j,26){
d3[i]+=d1[j][i];
d1[j][i]=0;
}
}
d3[c1]=0;
long c2;
if(c2=*rp-'a',c2>=0){
++rp;
if(c1==c2){
write(1,"0",1);
_exit(0);
}
long s=0;
rep(i,26){
s+=d3[i];
}
s-=d3[c2];
long c3;
while(c3=*rp-'a',c3>=0){
++rp;
if(c1==c3||c2==c3){
write(1,"0",1);
_exit(0);
}
c1=c2;
c2=c3;
}
d1[c1][c2]=s%MD;
}else{
rep(i,26){
d1[i][c1]=d3[i]%MD;
}
}
}
long z=0;
rep(i,26){
rep(j,26){
z+=d1[i][j];
}
}
z%=MD;
char wbuf[64],*wp=wbuf+sizeof wbuf;
wt(z);
write(1,wp,wbuf+sizeof wbuf-wp);
_exit(0);
}