提出 #41407140

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;

int main(){
	string s;
	cin >> s;
	
	vector<mint>dp(29);
	dp[0]=1;
	int used=0;
	
	for(auto c:s){
		vector<mint>new_dp(29);
		if('a'<=c&&c<='z'){
			new_dp[0]+=dp[0];
			for(int i=1;i<=26;i++)new_dp[i]+=dp[i];
			new_dp[28]+=dp[27];
			new_dp[28]+=dp[28];
		}else if('A'<=c&&c<='Z'){
			new_dp[1]+=dp[0];
			if((used>>(c-'A'))&1){
				for(int i=1;i<=26;i++)new_dp[27]+=dp[i];
			}else{
				int fix=__builtin_popcount(used);
				//i-fix個の中にcが入っていれば27へ
				//(i-fix)/(26-fix)
				if(fix<26){
					for(int i=1;i<=26;i++){
						new_dp[27]+=dp[i]*(i-fix)/(26-fix);
						if(i<26)new_dp[i+1]+=dp[i]*(26-i)/(26-fix);
					}
				}else{
					new_dp[27]+=dp[26];
				}
			}
			new_dp[27]+=dp[27];
			used|=1<<(c-'A');
		}else if(c=='?'){
			new_dp[0]+=dp[0]*26;
			new_dp[1]+=dp[0]*26;
			for(int i=1;i<=26;i++){
				new_dp[i]+=dp[i]*26;
				if(i<26)new_dp[i+1]+=dp[i]*(26-i);
				new_dp[27]+=dp[i]*i;
			}
			new_dp[27]+=dp[27]*26;
			new_dp[28]+=dp[27]*26;
			new_dp[28]+=dp[28]*26;
		}
		swap(dp,new_dp);
	}
	
	mint ans=0;
	for(auto x:dp)ans+=x;
	cout << ans.val() << endl;
}

提出情報

ジャッジ結果