結果

問題 No.2219 Re:010
コンテスト
ユーザー vjudge1
提出日時 2025-01-22 12:18:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 475 ms / 2,000 ms
コード長 1,258 bytes
コンパイル時間 2,339 ms
コンパイル使用メモリ 157,956 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2025-01-22 12:18:23
合計ジャッジ時間 5,965 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
#define c1 cout << 1 << " "
#define cen cout << endl
#define mod %998244353LL
using namespace std;
long long q=998244353;
long long mpow(long long a,long long b){
	if(b==1){
		return a;
	}
	if(b==0){
		return 1;
	}
	if(b%2==0){
		long long s=mpow(a,b/2)%q;
		return s%q*s%q;
	}
	else{
		long long s=mpow(a,b/2)%q;
		return s%q*s%q*a%q;
	}
}
int ar[200009]={0};
int ar1[200009]={0};
int br[200009]={0};
int br1[200009]={0};
signed main(){
	string str;
	cin >> str;
	str=" "+str;
	for(int i=1;i<str.size();i++){
		ar[i]=ar[i-1]+(str[i]=='0');
		ar1[i]=ar1[i-1]+(str[i]=='?');
//		c1;
	} 
	for(int i=str.size()-1;i>=1;i--){
		br[i]=br[i+1]+(str[i]=='0');
		br1[i]=br1[i+1]+(str[i]=='?');
	} 
	int sum=0;
	int num=br1[1];
	for(int i=2;i<str.size()-1;i++){
		if(str[i]=='1'||str[i]=='?'){
			if(str[i]=='?'){
				num--;
			}
			sum+=(ar[i-1] mod*br[i+1] mod*mpow(2,num)) mod;
			if(ar1[i-1]!=0){
				sum+=(ar1[i-1] mod*br[i+1] mod*mpow(2,num-1)) mod;
			}
			if(br1[i+1]!=0){
				sum+=(ar[i-1] mod*br1[i+1] mod*mpow(2,num-1)) mod;
			}
			if(ar1[i-1]!=0&&br1[i+1]!=0){
				sum+=(ar1[i-1] mod*br1[i+1] mod*mpow(2,num-2)) mod;
			}
			sum=sum mod;
			if(str[i]=='?'){
				num++;
			}
		}
	}
	cout << sum;
	return 0;
}
0