結果

問題 No.2219 Re:010
ユーザー vjudge1
提出日時 2025-01-22 11:18:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 1,115 bytes
コンパイル時間 2,042 ms
コンパイル使用メモリ 171,000 KB
実行使用メモリ 1,607,296 KB
最終ジャッジ日時 2025-01-22 11:18:53
合計ジャッジ時間 36,220 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 3 TLE * 4 MLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define el "\n"
#define sp " "
#define fi first
#define se second
#define inf 1e18
#define r0 return 0
#define int long long
#define F(i, a, b, c) for (int i = a; i <= b; i += c)
#define debug printf ("bug is in here\n")
#define TheEnd continue
#define base(s) s = sp + s
#define lcm(a, b) a * b / __gcd(a, b)
#define setp(x) fixed << setprecision(x)
#define p 998244353

using namespace std;

typedef long long ll;
typedef string str;
using ull = unsigned ll;

str s;
int n;
std::map<str, bool> b;
std::map<str, int> m;

inline int g(void) {
	int z = 0, zo = 0, zoz = 0;
	F(i, 1, n, 1) {
		if (s[i] == '0') {
			z++;
			zoz += zo;
		} else {
			zo += z;
		}
	}
	return zoz;
}

inline int f(int x) {
	if (b[s]) {
		return m[s];
	}
	if (x == n + 1) {
		return g();
	}
	if (s[x] != '?') {
		return f(x + 1);
	}
	s[x] = '0';
	int z = f(x + 1);
	s[x] = '1';
	int o = f(x + 1);
	s[x] = '?';
	b[s] = 1;
	m[s] = (z + o) % p;
	return m[s];
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	cin >> s;
	n = s.size();
	base(s);
	cout << f(1) << el;
	r0;
}
0