QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#761374 | #8080. Pa?sWorD | Lanthanmum | WA | 54ms | 4004kb | C++20 | 2.9kb | 2024-11-18 22:27:10 | 2024-11-18 22:27:11 |
Judging History
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3552kb
input:
4 a?0B
output:
86
result:
ok single line: '86'
Test #2:
score: 0
Accepted
time: 43ms
memory: 4004kb
input:
100000 1kQOIXnSMDlMqJcA8Ae6ov3DfVWAk0I16BgJ3tW1A6ERqBOy4kYizhqPUAU9DrUK26oQ8tgVQW0sRIcg0J2moqS6rRc5lh6QBtzFNfVDvU?sHilmsDIsywXDEeCy8bFracBGSwWNnkLa49E7d9JNXS1QsWPRoYV6IwSvdLdeYMczFmy7G56rxql6YXsX8AaWRLfxqukM5ovPzuSCTpSpN5?OaCE8xb8xu7xJ4A2pOHTOxe1EStiTlWMLeoM5qW6ULwCK4Dtcru8sjqaTilMzLvU27DcJnUhweXT80...
output:
483479164
result:
ok single line: '483479164'
Test #3:
score: 0
Accepted
time: 43ms
memory: 3776kb
input:
100000 hSilkqEibN5P3zsoXdREarzoRC94XflJB6OzigUfyu2ndtAvNBIeRyziL2k7DvqK5zs7O8Mjkw?LP6zyrT7?XLUJCdD7hTkhTmExwPNt58rb1ACY50PRJNBKktdq?m1CMQrFStmBh3DL5Uq2dLaQlByUpjK7gTHC78NclKgCJBrL37F?38KaQ?WVsMWzj4h4HCExAwXAo9M9s71nf0JyAFPs0d4tiPODAFboNfVbSldtpBKTtBznz1kLc7VKGPUkSFvoWEeEWbKQafX5PNEIJ95Xgi4oFeyBVgo4Y...
output:
647474736
result:
ok single line: '647474736'
Test #4:
score: 0
Accepted
time: 48ms
memory: 3832kb
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: 44ms
memory: 3780kb
input:
100000 xapS76EdJv9oTp54DzvJKSpzXq1dOFQL296LzyFdGu17n8QsxIbi8xcS1WlPqgjpJFomTmgX5bd1qysMjEcbF1N3eNGTQDxOo2qhRMSDUdUbmhgN0m5kYVwVGzQO2JIVEbRaO2WOl3qpf3J0XeVxOka3mkx6LOTtl5VndY1SRdHJ8KuKDNxQMPcaDc6frfsxnFADWkvaiMIkltyKGx3b0P6wJwqfD7twvy1DL?gc51otxt6mKG5NnSDsj2mFatU6KR?Ldt2?e3?oBMbztr6q8djvJEXUkSzSo79Qb...
output:
295912606
result:
ok single line: '295912606'
Test #6:
score: 0
Accepted
time: 49ms
memory: 3832kb
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: 54ms
memory: 3828kb
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'