#690369 (C) No.1646 Avoid Palindrome

• 問題: No.1646 Avoid Palindrome
• ユーザー: tails
• 提出日時: 2021-08-16 19:57:02
• 言語: C (gcc 12.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	61 ms; 5,248 KB
testcase_05	AC	61 ms; 5,248 KB
testcase_06	AC	57 ms; 5,248 KB
testcase_07	AC	61 ms; 5,248 KB
testcase_08	AC	62 ms; 5,248 KB
testcase_09	AC	56 ms; 5,248 KB
testcase_10	AC	59 ms; 5,248 KB
testcase_11	AC	58 ms; 5,248 KB
testcase_12	AC	62 ms; 5,248 KB
testcase_13	AC	62 ms; 5,248 KB
testcase_14	AC	57 ms; 5,248 KB
testcase_15	AC	56 ms; 5,248 KB
testcase_16	AC	44 ms; 5,248 KB
testcase_17	AC	53 ms; 5,248 KB
testcase_18	AC	54 ms; 5,248 KB
testcase_19	AC	63 ms; 5,248 KB
testcase_20	AC	46 ms; 5,248 KB
testcase_21	AC	56 ms; 5,248 KB
testcase_22	AC	57 ms; 5,248 KB
testcase_23	AC	65 ms; 5,248 KB
testcase_24	AC	65 ms; 5,248 KB
testcase_25	AC	53 ms; 5,248 KB
testcase_26	AC	53 ms; 5,248 KB
testcase_27	AC	60 ms; 5,248 KB
testcase_28	AC	62 ms; 5,248 KB
testcase_29	AC	21 ms; 5,248 KB
testcase_30	AC	19 ms; 5,248 KB
testcase_31	AC	20 ms; 5,248 KB
testcase_32	AC	20 ms; 5,248 KB
testcase_33	AC	21 ms; 5,248 KB
testcase_34	AC	3 ms; 5,248 KB
testcase_35	AC	1 ms; 5,248 KB
testcase_36	AC	1 ms; 5,248 KB
testcase_37	AC	1 ms; 5,248 KB
testcase_38	AC	1 ms; 5,248 KB
testcase_39	AC	1 ms; 5,248 KB
testcase_40	AC	1 ms; 5,248 KB
testcase_41	AC	1 ms; 5,248 KB
testcase_42	AC	1 ms; 5,248 KB
testcase_43	AC	21 ms; 5,248 KB

コンパイルメッセージ

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);
}