結果

問題 No.171 スワップ文字列(Med)
コンテスト
ユーザー uafr_cs
提出日時 2015-05-25 00:44:11
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 1,839 bytes
コンパイル時間 2,243 ms
コンパイル使用メモリ 77,924 KB
実行使用メモリ 55,720 KB
最終ジャッジ日時 2024-07-06 08:09:22
合計ジャッジ時間 3,709 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 1 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static final int SIZE = 26;
	
	public static long mod_inv(long a, long m){
	    return (a == 1 ? 1 : (1 - m*mod_inv(m%a, a)) / a + m);
	}
	
	public static long mod_fact(long n, long mod){
		long ret = 1;
		while(n >= mod - 1){
			ret *= (mod - 1);
			ret %= mod;
			
			n -= (mod - 1);
		}
		
		for(long i = 1; i <= n; i++){
			ret *= i;
			ret %= mod;
		}
		
		return ret;
	}
	
	public static long chinese_remainder(long[] as, long[] ms){
	    long prod = 1;
	    for(long m : ms){ prod *= m; }
	    
	    long ret = 0;
	    for(int i = 0; i < ms.length; i++){
	        final long M = prod / ms[i];
	        final long inv = mod_inv(M % ms[i], ms[i]);
	        
	        long a = as[i] - as[i] / prod * prod;
	        if(a < 0){ a += prod; }
	        
	        ret = (ret + M * inv * a % prod) % prod;
	    }
	    
	    return ret;
	}
	
	/* 573 = 3 * 191 なので, mod 3 と mod 191 の結果から, mod 573 の結果を中国剰余定理で合成すればいい.
	 * 階乗の計算には, Wilsonの定理を使えば良い. */
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		final char[] inputs = sc.next().toCharArray();
		
		char[] counter = new char[SIZE];
		for(final char c : inputs){
			counter[c - 'A']++;
		}
		
		long answer_3 = mod_fact(inputs.length, 3);
		long answer_191 = mod_fact(inputs.length, 191);
		for(int i = 0; i < SIZE; i++){
			if(counter[i] == 0){ continue; }
			
			answer_3 *= mod_inv(mod_fact(counter[i], 3), 3);
			answer_3 %= 3;
			answer_191 *= mod_inv(mod_fact(counter[i], 191), 191);
			answer_191 %= 191;
		}
		
		long answer_573 = chinese_remainder(new long[]{answer_3, answer_191},  new long[]{3, 191});
		
		System.out.println(answer_573 - 1);
	}
	
}
0