結果

問題 No.3178 free sort
コンテスト
ユーザー Thread
提出日時 2025-06-13 21:38:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 1,886 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 198,484 KB
実行使用メモリ 42,212 KB
最終ジャッジ日時 2025-06-13 21:38:13
合計ジャッジ時間 8,451 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

long long  md = 998244353;
const int MAXN = 1e6;

vector<long long > perm(MAXN+1,1),iperm(MAXN+1,1),inv(MAXN+1);

long long exGcd(long long a,long long b , long long &x,long long &y){
if(b==0){
    x=1,y=0;
    return a;
}
long long x1,y1;
long long d= exGcd(b,a%b,x1,y1);
x = y1;
y = x1 - (a/b)*y1;
return d;
}

void initCombi(){
    for(long long i =1 ;i<=MAXN;i++){
        perm[i]= (perm[i-1]*i + md )%md;
    }
    vector<long long > pre(MAXN+1,1),post(MAXN+1,1);
    long long tot = 1;
    for(long long i = 2;i<=MAXN;i++){
        pre[i]=(pre[i-1]*(i-1)+md)%md ;
        tot = (tot*i+md)%md;
    }
    for(long long i =MAXN-1;i>=1;i--){
        post[i]=(post[i+1]*(i+1)+md)%md;
    }
    long long itot , y;
    exGcd(tot,md,itot,y);
    itot = (itot%md+ md)%md;
    for(int i =1;i<=MAXN;i++){
        inv[i] = ((pre[i]*post[i]%md)*itot%md + md )%md;
    }
    
    for(long long i = 1;i<=MAXN;i++){
        iperm[i]= (iperm[i-1] * inv[i] +md)%md;
    }
}

long long nCr(int n , int r){
    return ((perm[n]*iperm[n-r])%md)*iperm[r]%md;
}

void solve() {
 // definately i cannot store that big number 
 int mod = 998244353;
 // need to do the comp on the fly 
 string s; 
 cin>>s; 
 vector<int> digit(10,0);
 for(int i =0;i<s.size();i++){
    digit[s[i]-'0']++;
 }
 // need to get the factorial and reverse fact mod m 
 long long ans = (s.size()-digit[0]);

 ans = (ans*perm[s.size()-1]%md + md )%md;

 for(int i=0;i<10;i++){
    ans = (ans*iperm[digit[i]]%md + md )%md;
 }
 cout<<ans;




}



int main(){
    initCombi();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.flush();
    cout<<fixed<<setprecision(9);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif  
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
0