結果

問題 No.3178 free sort
ユーザー msksknkn
提出日時 2025-06-14 17:19:54
言語 Java
(openjdk 23)
結果
AC  
実行時間 454 ms / 2,000 ms
コード長 1,435 bytes
コンパイル時間 3,677 ms
コンパイル使用メモリ 79,812 KB
実行使用メモリ 51,092 KB
最終ジャッジ日時 2025-06-14 17:20:18
合計ジャッジ時間 23,365 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
public class Main {
	public static long MOD = 998244353;
	public static long[] kaijo;
	public static long[] div;
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int n = s.length();
		int zero = 0;
		int[] num = new int[10];
		for(int i = 0;i < s.length();i++) {
			int a = s.charAt(i) - '0';
			num[a]++;
		}kaijo = new long[n + 1];
		div = new long[n + 1];
		kaijo[0] = 1;
		div[0] = 1;
		for(int i = 1;i <= n;i++) {
			kaijo[i] = kaijo[i - 1] * (long)i % MOD;
			div[i] = pow(kaijo[i],MOD - 2);
		}long ans = 0;
		for(int i = 1;i <= 9;i++) {
			if(num[i] == 0)continue;
			int rem = n - 1;
			long add = 1;
			for(int j = 0;j < 9;j++) {
				if(i != j) {
					add = (add * combination(rem,num[j])) % MOD;
					rem -= num[j];
				}else {
					add = (add * combination(rem,num[j] - 1)) % MOD;
					rem -= num[j] - 1;
				}//System.out.print(rem + " ");
			}ans += add;
			//System.out.println(" ");
		}System.out.print(ans % MOD);
	}public static long combination(int a,int b) {
		if(a < b)return 0;
		return kaijo[a] * div[b] % MOD * div[a - b] % MOD;
	}
	public static long pow(long a,long b) {
		long ret = 1;
		long val = a % MOD;
		long comp = 1;
		for(int i = 0;i < 40;i++) {
			if((b &comp) != 0) {
				ret = (ret * val) % MOD;
			}val = (val * val) % MOD;
			comp *= 2L;
		}return ret;
	}

}
0