結果

問題 No.171 スワップ文字列(Med)
コンテスト
ユーザー kuuso1
提出日時 2015-03-23 00:10:06
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 25 ms / 1,000 ms
コード長 3,912 bytes
コンパイル時間 769 ms
コンパイル使用メモリ 116,656 KB
実行使用メモリ 18,432 KB
最終ジャッジ日時 2024-06-29 00:18:17
合計ジャッジ時間 1,524 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;


class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long[] R=new long[26];
		for(int i=0;i<S.Length;i++){
			R[S[i]-'A']++;
		}
		ModComb2.Init(3);
		long m3=ModComb2.Mod_nCr(R.Sum(),R);
		ModComb2.Init(191);
		long m191=ModComb2.Mod_nCr(R.Sum(),R);
		
		long m573=alg.CRT(3,m3,191,m191);
		Console.WriteLine( (m573-1+573)%573 );
	}
	String S;
	public Sol(){
		S=rs();
	}




	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}


class ModComb2{
	public static long P=0;
	static long[] Fact;
	static long mod=0;
	public static void Init(long p){
		// k!(k<p) mod p テーブルを作る。pのサイズに注意
		P=p;mod=p;
		Fact=new long[(int)p];
		Fact[0]=1;
		Fact[1]=1;
		for(int i=2;i<p;i++)Fact[i]=(i*Fact[i-1])%mod;
	}
	
	
	public static long ModInv(long x){
		//拡張ユークリッドの互除法でmod逆元を求める
		//ax + mod * y = 1 で mod取れば ax = 1 になるから xがaの逆元になる
		//逆元が存在しない→0を返す。
		long a=0,b=0,c=0;
		if(x==0)return 0;
		ExtGCD(x,mod,ref a,ref b,ref c);
		if(c!=1)return 0;
		return (a+mod)%mod;
	}
	
	public static long ModFact(long n,ref long e){
		// n!%mod を計算する。
		// n!= a * p^e として、a%modとeを計算する
		
		//e は n/p + n/p^2 + n/p^3 +... で求まる
		//a は n! = {(1*2*..*p-1)} * {(p+1)*(p+2)*...*(p+p-1)} 
		//          *...* {((n/p-1)*p+1)*((n/p-1)*p+2)*...*((n/p-1)*p+p-1)} * {((n/p)*p+1)*...*((n/p)*p+(n%p))}
		//          *p(1*2*...*(n/p));
		//より、  = {(1*2*..*p-1)}^(n/p)*{((n/p)*p+1)*...*((n/p)*p+(n%p))}* {(n/p)のa部分}
		//で、    = ((p-1)!)^(n/p) * Fact(n%p) * {(n/p)のa部分}  
		//さらに  = ((n/p)%2==0?1:-1)* Fact(n%p) * {(n/p)のa部分}   となる
		e=0;
		if(n==0)return 1;
		long res=ModFact(n/mod,ref e);
		e+=n/mod;
		
		return (n/mod)%2==0?(Fact[n%mod]*res)%mod:((mod-Fact[n%mod])*res)%mod;
	}
	
	
	public static long Mod_nCr(long n,long[] r){
		long e=0;
		long[] ek=new long[r.Length];
		long[] denk=new long[r.Length];
		long num=ModFact(n,ref e);
		for(int i=0;i<r.Length;i++){
			denk[i]=ModFact(r[i],ref ek[i]);
		}
		if(e>ek.Sum())return 0;
		long ret=num;
		for(int i=0;i<r.Length;i++){
			ret =(ret*ModInv(denk[i]))%mod;
		}
		return ret;
	}
	
	public static void ExtGCD(long x,long y,ref long a,ref long b,ref long c){
		long r0=x;long r1=y;
		long a0=1;long a1=0;
		long b0=0;long b1=1;
		long q1,r2,a2,b2;
		while(r1>0){
			q1=r0/r1;
			r2=r0%r1;
			a2=a0-q1*a1;
			b2=b0-q1*b1;
			r0=r1;r1=r2;
			a0=a1;a1=a2;
			b0=b1;b1=b2;
		}
		c=r0;
		a=a0;
		b=b0;
	}
}


class alg{
	public static long CRT(long m1,long a,long m2,long b){
		// ChineseReminderTheorem
		// m1,m2:coprime
		// x%m1==a,x%m2==b => return x%m1m2
		//
		// ∃u,v  s.t.  u*m1+v*m2==1;
		//   return x=(b*u*m1+a*v*m2)%(m1m2);
		long u=0,v=0,c=0;
		ExtGCD(m1,m2,ref u,ref v,ref c);
		long mm=m1*m2;
		b*=u;b%=mm;b*=m1;b%=mm;
		a*=v;a%=mm;a*=m2;a%=mm;
		return (a+b)%mm;
	}


	public static void ExtGCD(long x,long y,ref long a,ref long b,ref long c){
		long r0=x;long r1=y;
		long a0=1;long a1=0;
		long b0=0;long b1=1;
		long q1,r2,a2,b2;
		while(r1>0){
			q1=r0/r1;
			r2=r0%r1;
			a2=a0-q1*a1;
			b2=b0-q1*b1;
			r0=r1;r1=r2;
			a0=a1;a1=a2;
			b0=b1;b1=b2;
		}
		c=r0;
		a=a0;
		b=b0;
	}
}
0