期末考试考完了…开始补题了
最近几场ATC的ABC都很简单,前五题都是普及组左右,因此目前的目标就是能够稳出F
这次F的读题没读明白,读错了,实际上是可以乱序,因此就是一个数学组合题:
#define int LL
const int N = 5010,mod=998244353;
int n,m,k;
int f[N][N],fac[N],inv[N],finv[N],freq[27];
string s;
//f[i][j]表示前i个字母组成的长度为j的子序列的数量
//f[i][j]+=for(k=0;k<=min(j,freq[i]);k++) f[i-1][j-k]*C(k,j)
void init(){
fac[0]=fac[1]=1;
inv[1]=1;
finv[0]=finv[1]=1;
rep(i,2,5001){
fac[i]=fac[i-1]*i%mod;
inv[i]=fpower(i,mod-2,mod);
finv[i]=finv[i-1]*inv[i]%mod;
// debug(finv[i]);
}
}
LL C(int a,int b){
if(b>a||a<0||b<0) return 0;
// debug(fac[a]); debug(finv[b]);debug(finv[b-a]); debug(finv[2]);
return fac[a]*finv[b]%mod*finv[a-b]%mod;
}
void solve(){
init();
cin >> s; n=s.size();
for(auto u:s) freq[u-'a']++;
f[0][0]=1;
rep(i,0,25)
rep(j,0,n){
rep(k,0,min(j,freq[i])){
f[i+1][j] += f[i][j-k] * C(j,k);
f[i+1][j] %= mod;
}
}
LL ans = 0;
rep(i,1,n) (ans+=f[26][i])%=mod;
print(ans);
}
//=================================
signed main(){
solve();
return 0;
}