結果

問題 No.1195 数え上げを愛したい(文字列編)
ユーザー kaagekaage
提出日時 2020-08-20 22:02:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,749 ms / 3,000 ms
コード長 2,027 bytes
コンパイル時間 2,617 ms
コンパイル使用メモリ 174,604 KB
実行使用メモリ 33,172 KB
最終ジャッジ日時 2024-04-21 19:21:07
合計ジャッジ時間 40,244 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,749 ms
33,080 KB
testcase_01 AC 2,687 ms
32,956 KB
testcase_02 AC 2,713 ms
32,824 KB
testcase_03 AC 242 ms
11,852 KB
testcase_04 AC 299 ms
12,244 KB
testcase_05 AC 283 ms
26,692 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 437 ms
7,916 KB
testcase_09 AC 2,583 ms
33,172 KB
testcase_10 AC 1,422 ms
18,692 KB
testcase_11 AC 2,320 ms
32,284 KB
testcase_12 AC 2,123 ms
32,040 KB
testcase_13 AC 1,783 ms
20,680 KB
testcase_14 AC 1,100 ms
17,880 KB
testcase_15 AC 1,355 ms
17,004 KB
testcase_16 AC 1,204 ms
17,492 KB
testcase_17 AC 451 ms
8,296 KB
testcase_18 AC 2,221 ms
32,092 KB
testcase_19 AC 2,131 ms
32,172 KB
testcase_20 AC 1,812 ms
20,492 KB
testcase_21 AC 2,297 ms
32,808 KB
testcase_22 AC 1,706 ms
19,872 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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

const int MOD=998244353;
const 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']++;
	}
	sort(cnt,cnt+26);
	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