题意：
给出一个串，可能?、小写字母，大写字母、数字。
小写字母可以变成当前小写字母的小写或者大写形式。
数字和大写只能是当前形式。
问号可以变成另外三种形式。
现在要求相同的字符不相邻，且字符串中同时出现三种字符形式的方案数。
设dp[i][j][k]，表示第i个位置为j，且当前状态为k的方案数。
k是状压的形式:[0 0 0]三个位置分别表示数字、小写和大写，其范围为[0,7]
当前的位置j通过映射,[1~62]对应[0 ~ 9, a ~ z, A ~ Z]
转移方程:
对于每个k和当前的h进行下列方程转移。
\[dp[i][h][st(h)|k]=\sum_{j=1\&\&j!=h}^{62}dp[i-1][j][k]
\]
然而这样如果遇到问号，复杂度是\((k=7)*(j=62)*(当前的h=62)*(总长1e5)\)转移，过不了。
这里考虑先对于每个k，提前把\(\sum_{j=1}^{62}dp[i-1][j][k]\)处理好，然后对对应的h，特别的减去\(dp[i-1][h][k]\),写作下式：
\[dp[i][h][st(h)|k]=\sum_{j=1}^{62}dp[i-1][j][k]-dp[i-1][h][k]
\]
则复杂度转化为\((k=7)*(j=62+当前的h=62)*(总长1e5)\)
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define int long long
const int N = 1e5+7;
int dp[2][80][10],tmp[10];
char ch[80];
map<char,int>mp;
const int mod = 998244353;
int st(int y)
{
char x=ch[y];
if(isdigit(x))
{
return 1;
}
if(islower(x))
{
return 2;
}
if(isupper(x))
{
return 4;
}
return 0;
}
signed main()
{
IOS;
int n;
cin>>n;
string s;
cin>>s;
s=' '+s;
int cnt=0;
for(int i=0;i<=9;i++)
{
ch[++cnt]=i+'0';
mp[i+'0']=cnt;
}
for(char x='a';x<='z';x++)
{
ch[++cnt]=x;
mp[x]=cnt;
}
for(char x='A';x<='Z';x++)
{
ch[++cnt]=x;
mp[x]=cnt;
}
int id=mp[s[1]];
if(st(id)==0)
{
//问号
for(int i=1;i<=62;i++)
{
dp[1][i][st(i)]=1;
}
}else if(st(id)==1)
{
//数字
dp[1][id][st(id)]=1;
}else if(st(id)==2)
{
//小写
dp[1][id][st(id)]=1;
dp[1][id+26][st(id+26)]=1;
}else if(st(id)==4)
{
//大写
dp[1][id][st(id)]=1;
}
int cur=1;
for(int i=2;i<=n;i++)
{
for(int k=1;k<=7;k++)
{
tmp[k]=0;
}
for(int j=1;j<=62;j++)
{
for(int k=1;k<=7;k++)
{
//把所有k相同的状态做前缀和转移
tmp[k]+=dp[cur][j][k];
tmp[k]%=mod;
//滚动数组清空
dp[cur^1][j][k]=0;
}
}
int now=mp[s[i]];
for(int k=1;k<=7;k++)
{
if(st(now)==0)
{
for(int id=1;id<=62;id++)
{
//问号的时候，枚举当前
dp[cur^1][id][k|st(id)]+=tmp[k]-dp[cur][id][k];
dp[cur^1][id][k|st(id)]=(dp[cur^1][id][k|st(id)]%mod+mod)%mod;
}
}else if(st(now)==1)
{
//[1,10]
int id=mp[s[i]];
dp[cur^1][id][k|st(id)]+=tmp[k]-dp[cur][id][k];
dp[cur^1][id][k|st(id)]=(dp[cur^1][id][k|st(id)]%mod+mod)%mod;
}else if(st(now)==2)
{
//小写
int id=mp[s[i]];
dp[cur^1][id][k|st(id)]+=tmp[k]-dp[cur][id][k];
dp[cur^1][id][k|st(id)]=(dp[cur^1][id][k|st(id)]%mod+mod)%mod;
id+=26;
dp[cur^1][id][k|st(id)]+=tmp[k]-dp[cur][id][k];
dp[cur^1][id][k|st(id)]=(dp[cur^1][id][k|st(id)]%mod+mod)%mod;
}else if(st(now)==4)
{
//大写
int id=mp[s[i]];
dp[cur^1][id][k|st(id)]+=tmp[k]-dp[cur][id][k];
dp[cur^1][id][k|st(id)]=(dp[cur^1][id][k|st(id)]%mod+mod)%mod;
}
}
cur=cur^1;
}
int maxn=0;
for(int i=1;i<=62;i++)
{
maxn=maxn+dp[cur][i][7];
maxn%=mod;
}
cout<<maxn<<endl;
}