QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#761377#8080. Pa?sWorDLanthanmumWA 53ms4080kbC++202.9kb2024-11-18 22:28:202024-11-18 22:28:23

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 22:28:23]
  • 评测
  • 测评结果:WA
  • 用时:53ms
  • 内存:4080kb
  • [2024-11-18 22:28:20]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>

//vector最多二维
#define debug(x) cerr<<"check"<<" "<<x<<'\n'
#define INF INT_MAX
#define eps 1e-6
using namespace std;
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<ll> vl;
typedef vector<vector<ll> > vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef double d;
#define time mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());//稳定随机卡牛魔 ull
constexpr int N=1e5+9;
const int mod=998244353;
bool upper(char s){
    return 'A'<=s && s<='Z';
}
bool lower(char s){
    return 'a'<=s && s<='z';
}
bool dig(char s){
    return '0'<=s && s<='9';
}
bool q(char s){
    return (s=='?');
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    auto solve = [&]() {
    	int n;
    	cin>>n;
    	string s;
    	cin>>s;
    	s=" "+s;
    	vi flag(4);//A,a,0
    	auto get=[&](){
    		vii dp(2,vi(70));//滚动, 1,26 A, 27-52 a,53-62 0,9  63 tot
    		dp[0][63]=1;
    		for(int i=1;i<=n;i++){
 				for(int j=1;j<=63;j++){
 					dp[i&1][j]=0;
				}
 				if(upper(s[i])){
 					if(flag[0])return 0;
 					dp[i&1][s[i]-'A'+1]=dp[(i-1)&1][63]-dp[(i-1)&1][s[i]-'A'+1];
 				}else if(lower(s[i])){
 					if(flag[1] && flag[0])return 0;
 					if(!flag[1]){
 						dp[i&1][s[i]-'a'+27]=dp[(i-1)&1][63]-dp[(i-1)&1][s[i]-'a'+27];
 					}
 					if(!flag[0]){
 						dp[i&1][s[i]-'a'+1]=dp[(i-1)&1][63]-dp[(i-1)&1][s[i]-'a'+1];
 					}
 				}else if(dig(s[i])){
 					if(flag[2])return 0;
 					dp[i&1][s[i]-'0'+53]=dp[(i-1)&1][63]-dp[(i-1)&1][s[i]-'0'+53];
 				}else{//?
 					for(int j=1;j<=62;j++){
	 					if(flag[0] && j>=1 && j<=26)continue;
	                	if(flag[1] && j>=27 && j<=52)continue;
	                	if(flag[2] && j>=53)continue;
 						dp[i&1][j]=dp[(i-1)&1][63]-dp[(i-1)&1][j];
 					}
 				}
 				//tot
 				for(int j=1;j<=62;j++){
 					dp[i&1][63]=(dp[i&1][63]+dp[i&1][j])%mod;
 				}
    		}
    		return dp[n&1][63];
    	};
    	ll ans=0;
    	// for(int i=0;i<(1<<3);i++){
    		// int sign=1;
    		// for(int k=0;k<3;k++)flag[k]=0;
    		// for(int j=0;j<3;j++){
    			// if(i&1<<j){	
    				// flag[j]=1;
    				// sign=-sign;
    			// }
    		// }
    		// ans+=sign*get();
    	// }
    	ans+=get();//000
    	flag[0]=1,flag[1]=0,flag[2]=0,ans-=get();//100
	    flag[0]=0,flag[1]=1,flag[2]=0,ans-=get();//010
    	flag[0]=0,flag[1]=0,flag[2]=1,ans-=get();//001
    	flag[0]=1,flag[1]=1,flag[2]=0,ans+=get();//110
    	flag[0]=0,flag[1]=1,flag[2]=1,ans+=get();//011
    	flag[0]=1,flag[1]=0,flag[2]=1,ans+=get();//101
    	flag[0]=1,flag[1]=1,flag[2]=1,ans-=get();//111
    	cout<<((ans%mod+mod)%mod)<<'\n';
    };
    int t=1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

4
a?0B

output:

86

result:

ok single line: '86'

Test #2:

score: 0
Accepted
time: 43ms
memory: 3792kb

input:

100000
1kQOIXnSMDlMqJcA8Ae6ov3DfVWAk0I16BgJ3tW1A6ERqBOy4kYizhqPUAU9DrUK26oQ8tgVQW0sRIcg0J2moqS6rRc5lh6QBtzFNfVDvU?sHilmsDIsywXDEeCy8bFracBGSwWNnkLa49E7d9JNXS1QsWPRoYV6IwSvdLdeYMczFmy7G56rxql6YXsX8AaWRLfxqukM5ovPzuSCTpSpN5?OaCE8xb8xu7xJ4A2pOHTOxe1EStiTlWMLeoM5qW6ULwCK4Dtcru8sjqaTilMzLvU27DcJnUhweXT80...

output:

483479164

result:

ok single line: '483479164'

Test #3:

score: 0
Accepted
time: 43ms
memory: 3724kb

input:

100000
hSilkqEibN5P3zsoXdREarzoRC94XflJB6OzigUfyu2ndtAvNBIeRyziL2k7DvqK5zs7O8Mjkw?LP6zyrT7?XLUJCdD7hTkhTmExwPNt58rb1ACY50PRJNBKktdq?m1CMQrFStmBh3DL5Uq2dLaQlByUpjK7gTHC78NclKgCJBrL37F?38KaQ?WVsMWzj4h4HCExAwXAo9M9s71nf0JyAFPs0d4tiPODAFboNfVbSldtpBKTtBznz1kLc7VKGPUkSFvoWEeEWbKQafX5PNEIJ95Xgi4oFeyBVgo4Y...

output:

647474736

result:

ok single line: '647474736'

Test #4:

score: 0
Accepted
time: 43ms
memory: 3768kb

input:

100000
?t?T?1?I?9?L7v?9?q?s?r?BM?n?6?u?M?n0?fR?G?k?s?RB?vwP?7?7?p?Y0?e?M?T?l?UX6?W?n?uz?D?y?x?1?X?z?N?z?O?8?z?j?Rs?D?p?M?91?u?HJrO?U?T?UN?4?yR1?n?xn?7?K?u?kbmz4?6?s?u?m?y?1?1?9?8Uy?1?Pm?0?x?z?E?y?4?F?zlMtF?e7?lF?r4R?4G?6?J?R?b?s4wc?q?L?3?9?N?zD?S?nJ?BaB?e?G?b?LIoP?H?T?vrC?Y?g?H?re?H?s?Qr?s?sGer?J?H?...

output:

955136381

result:

ok single line: '955136381'

Test #5:

score: 0
Accepted
time: 43ms
memory: 3836kb

input:

100000
xapS76EdJv9oTp54DzvJKSpzXq1dOFQL296LzyFdGu17n8QsxIbi8xcS1WlPqgjpJFomTmgX5bd1qysMjEcbF1N3eNGTQDxOo2qhRMSDUdUbmhgN0m5kYVwVGzQO2JIVEbRaO2WOl3qpf3J0XeVxOka3mkx6LOTtl5VndY1SRdHJ8KuKDNxQMPcaDc6frfsxnFADWkvaiMIkltyKGx3b0P6wJwqfD7twvy1DL?gc51otxt6mKG5NnSDsj2mFatU6KR?Ldt2?e3?oBMbztr6q8djvJEXUkSzSo79Qb...

output:

295912606

result:

ok single line: '295912606'

Test #6:

score: 0
Accepted
time: 48ms
memory: 3840kb

input:

100000
?V?k?2?d?u?l?S?1?g?m?8?G?N?J?S?g?DS?y?B?c?1?j?p9?T?i?o?M?S?H?K?L?G?0?w?3?K?b?s?L?Q?a?U?G?t?5?W?8s?H?q?5?p3?Pn?e?B?R?R?E?fM?B?q?R?A?m?W?m?X?i?8?2?Y?e?9?L?q?V?i?n?N?D?t?V?G?S?g?g?7?i?G?O?z?i?C?z?7?3?g?l?l?o?m?K?K?I?nW?c?w?T?o?k?Y?C?I?7?X?z?l?H?rS?9?M?S?s?B?1?T?n?E?C?Y?W?Jf?L?X?y?k?f?1?d?6?c?D?M...

output:

618729923

result:

ok single line: '618729923'

Test #7:

score: -100
Wrong Answer
time: 53ms
memory: 4080kb

input:

100000
?????????????????3?????l???????4??J????????6???C?????G????????????????????????????????h???????????????????????????4???9?????????????????????????6??C????w????????????????????????????????????????E??????8???????????????????????????????F?????????????6???????????????????L?????b???????????????d????...

output:

621192263

result:

wrong answer 1st lines differ - expected: '268229202', found: '621192263'