結果

問題 No.1195 数え上げを愛したい（文字列編）
コンテスト
ユーザー kaage
提出日時 2020-08-20 21:57:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,016 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 175,824 KB
実行使用メモリ 38,096 KB
最終ジャッジ日時 2024-10-13 18:04:17
合計ジャッジ時間 16,402 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

constexpr int MOD=998244353;
constexpr int r=3;

ll ppow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

class Fact{
	vector<ll>fact;
	vector<ll>inv;
public:
	Fact(){}
	Fact(int n){
		n=n*2+10;
		fact=inv=vector<ll>(n);
		fact[0]=inv[0]=1;
		for(int i=1;i<n;i++){
			fact[i]=(fact[i-1]*i)%MOD;
		}
		inv[n-1]=ppow(fact[n-1],MOD-2);
		for(int i=n-2;i>=0;i--){
			inv[i]=(inv[i+1]*(i+1))%MOD;
		}
	}
	ll get(int n){
		return fact[n];
	}
	ll get_inv(int n){
		return inv[n];
	}
	ll nPr(int n,int r){
		return fact[n]*inv[n-r]%MOD;
	}
	ll nCr(int n,int r){
		return nPr(n,r)*inv[r]%MOD;
	}
	ll nrP(int n,int r){
		return nPr(n+r,n);
	}
	ll nrC(int n,int r){
		return nCr(n+r,n);
	}
};

void dft(vector<ll>&f,bool inv=false){
	int n=f.size();
	rep(i,n){
		int b=31-__builtin_clz(n);
		int j=0;
		rep(k,b){
			if(i>>k&1)j|=1<<(b-k-1);
		}
		if(i<j)swap(f[i],f[j]);
	}
	for(int i=2;i<=n;i<<=1){
		ll w=ppow(r,(MOD-1)/i);
		if(inv)w=ppow(w,MOD-2);
		for(int k=0;k<n;k+=i){
			ll x=1;
			rep(j,i/2){
				ll t=x*f[k+j+i/2]%MOD,u=f[k+j];
				f[k+j]=(u+t)%MOD;
				f[k+j+i/2]=(u+MOD-t)%MOD;
				(x*=w)%=MOD;
			}
		}
	}
	if(inv){
		ll n_inv=ppow(n,MOD-2);
		rep(i,n)(f[i]*=n_inv)%=MOD;
	}
}

vector<ll>multiply(vector<ll>A,vector<ll>B){
	int m=A.size()+B.size();
	int N=1;while(N<A.size()+B.size())N<<=1;
	A.resize(N);B.resize(N);
	dft(A,0);
	dft(B,0);
	vector<ll>f(N);
	rep(i,N)f[i]=A[i]*B[i]%MOD;
	dft(f,1);
	f.erase(f.begin()+m-1,f.end());
	return f;
}

int cnt[26];
int main(){
	string s;cin>>s;
	for(char c:s){
		cnt[c-'a']++;
	}
	Fact fac(s.size()+1);
	vector<ll>A(1);
	A[0]=1;
	rep(i,26){
		vector<ll>B(cnt[i]+1);
		rep(j,A.size())(A[j]*=fac.get_inv(j))%=MOD;
		rep(j,B.size())B[j]=fac.get_inv(j);
		auto res=multiply(A,B);
		rep(j,res.size())(res[j]*=fac.get(j))%=MOD;
		A=res;
	}
	ll ans=0;
	for(int i=1;i<A.size();i++)(ans+=A[i])%=MOD;
	cout<<ans<<endl;
}
0