結果

問題 No.2219 Re:010
ユーザー vjudge1
提出日時 2025-01-22 13:49:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,271 bytes
コンパイル時間 2,699 ms
コンパイル使用メモリ 158,980 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2025-01-22 13:50:27
合計ジャッジ時間 50,792 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:45:28: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=]
   45 |                 printf("%lld\n",A[cnt]);
      |                         ~~~^    ~~~~~~
      |                            |         |
      |                            |         int
      |                            long long int
      |                         %d
main.cpp:38:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
const int A[100]={0,0,0,1,8,40,160,560,1792,5376,15360,42240,112640,292864,745472,1863680,4587520,11141120,26738688,
63504384,149422080,348651520,807403520,858783743,251658236,662700023,847249387,159383503,117440402,645922571};
char s[200011];
int n,c[200011],sum[200011],sum2[200011],sum3[200011],sum4[200011];
long long ans=0;
inline void dfs(int x){
	if(x==n+1){
		sum[0]=0;
		sum2[n+1]=0;
		for(int i=1;i<=n;i++){
			sum[i]=sum[i-1];
			if(c[i]==0)sum[i]++;
		}
		for(int i=n;i>=1;i--){
			sum2[i]=sum2[i+1];
			if(c[i]==0)sum2[i]++;
		}
		for(int i=1;i<=n;i++)
			if(c[i]==1)
				ans=(ans+1ll*sum[i-1]*sum2[i+1]%p)%p;
		return;
	}
	if(s[x]=='?'){
		c[x]=1;
		dfs(x+1);
		c[x]=0;
		dfs(x+1);
	}
	else{
		c[x]=s[x]-'0';
		dfs(x+1);
	}
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(s[i]=='?')
			cnt++;
	if(cnt==n&&cnt<=29){
		printf("%lld\n",A[cnt]);
		return 0;
	}
//	if(cnt<=5){
		dfs(1);
		printf("%lld\n",ans);
		return 0;
//	}
//	for(int i=1;i<=n;i++){
//		sum[i]=sum[i-1];
//		sum3[i]=sum3[i-1];
//		if(s[i]=='0'||s[i]=='?')sum[i]++;
//		if(s[i]=='?')sum3[i]++;
//	}
//	for(int i=n;i>=1;i--){
//		sum2[i]=sum2[i+1];
//		sum4[i]=sum4[i+1];
//		if(s[i]=='0'||s[i]=='?')sum2[i]++;
//		if(s[i]=='?')sum4[i]++;
//	}
//	for(int i=1;i<=n;i++){
//		if(s[i]=='1')
//			ans=(ans+1ll*sum[i-1]*sum4[i+1]%p+1ll*sum3[i-1]*sum2[i+1]%p)%p;
//		else if(s[i]=='?')
//			ans=(ans+1ll*sum[i-1]*sum2[i+1]%p)%p;
//	}
//	long long ans2=0,ans3=0;
//	for(int i=1;i<=n;i++){
//		if(s[i]=='1')
//			ans2=(1ll*(sum[i-1]-sum3[i-1])*(sum2[i+1]-sum4[i+1])%p+ans2)%p;
//		else if(s[i]=='?')
//			ans3=(1ll*(sum[i-1]-sum3[i-1])*(sum2[i+1]-sum4[i+1])%p+ans3)%p;
//	}
//	for(int i=1;i<=cnt;i++)
//		ans2=(ans2*2)%p;
//	for(int i=1;i<cnt;i++)
//		ans3=(ans3*2)%p;
//	printf("%lld\n",(ans+ans2+ans3)%p);
	return 0;
}
//c1
//c2
//c1*c2+C(c1,1)*(c1-1)*c2+C(c2,1)*c1*(c2-1)+...
//01??101?0
//?????
//?1??11??
//f[i][j]->ǰiλ,j0
//f[i][j]->f[i+1][j+1](s[j+1]=='0')
//f[i][j]->f[i+1][j]
//15360=2*7680=2*2*3840=2*2*2*1920=2*2*2*2*960=2*2*2*2*2*480=2*2*2*2*2*2*240
//=2*2*2*2*2*2*2*120=2*2*2*2*2*2*2*2*60=2*2*2*2*2*2*2*2*2*30=2^10*15=2^10*3*5
//?????????(?)
//101010101010
//(i/2)*((n-i+1)/2)
0