結果
| 問題 | No.1646 Avoid Palindrome |
| コンテスト | |
| ユーザー |
👑  tails
|
| 提出日時 | 2021-08-16 19:23:44 |
| 言語 | C (gcc 15.2.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,732 bytes |
| 記録 | |
| コンパイル時間 | 324 ms |
| コンパイル使用メモリ | 29,248 KB |
| 最終ジャッジ日時 | 2026-01-07 14:49:29 |
| 合計ジャッジ時間 | 1,108 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.c: 関数 ‘m_zero’ 内:
main.c:30:9: エラー: 関数 ‘memset’ の暗黙的な宣言です [-Wimplicit-function-declaration]
30 | memset(&r,0,sizeof r);
| ^~~~~~
main.c:1:1: 備考: include ‘<string.h>’ or provide a declaration of ‘memset’
+++ |+#include <string.h>
1 | #pragma GCC optimize("Ofast")
main.c:30:9: 警告: 組み込み関数 ‘memset’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
30 | memset(&r,0,sizeof r);
| ^~~~~~
main.c:30:9: 備考: include ‘<string.h>’ or provide a declaration of ‘memset’
main.c: トップレベル:
main.c:145:1: エラー: 戻り値の型をデフォルトの ‘int’ にします [-Wimplicit-int]
145 | main(){
| ^~~~
main.c: 関数 ‘main’ 内:
main.c:146:17: エラー: too many arguments to function ‘mmap’; expected 0, have 6
146 | char*rp=mmap(0l,1l<<25,1,2,0,0ll);
| ^~~~ ~~
main.c:4:6: 備考: ここで宣言されています
4 | char*mmap();
| ^~~~
main.c:150:25: エラー: 関数 ‘write’ の暗黙的な宣言です [-Wimplicit-function-declaration]
150 | write(1,"26",2);
| ^~~~~
main.c:154:17: エラー: 関数 ‘_exit’ の暗黙的な宣言です [-Wimplicit-function-declaration]
154 | _exit(0);
| ^~~~~
main.c:154:17: 警告: 組み込み関数 ‘_exit’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
main.c:235:9: 警告: 組み込み関数 ‘_exit’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
235 | _exit(0);
| ^~~~~
ソースコード
#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 c=*rp++-'a';
if(c<0){
break;
}
rep(i,26){
if(i!=c){
rep(j,26){
if(j!=c){
d2[i][c]+=d1[j][i];
}
}
}
}
nextd();
}
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);
}