AtCoder Beginner Contest 234 F - Reordering

本文主要是介绍AtCoder Beginner Contest 234 F - Reordering，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

期末考试考完了…开始补题了
最近几场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;
}

这篇关于AtCoder Beginner Contest 234 F - Reordering的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！