Hatena::Grouptopcoder

kuuso1の日記

2015-02-24

Ad Infinitum 10

| 02:12 | Ad Infinitum 10 - kuuso1の日記 を含むブックマーク はてなブックマーク - Ad Infinitum 10 - kuuso1の日記

https://www.hackerrank.com/contests/infinitum10/challenges

HackerRankで不定期開催の48時間コンテスト数学にクローズアップした問題が出題されます。

6完/8問、37位/938人と結構よくできた。A-Eはまとめて記事にします。Fは別記事で。

A: Sherlock and Moving Tiles

  • XY平面に(0,0)(L,0)(L,0)(L,L)が成す正方形が2枚あり、Y=Xに沿って一つは速度S1、もう一つは速度S2で移動する
  • このとき、オーバーラップしている面積がqiとなる時刻を求めるQ個のクエリに答えよ

(制約)1≤L,S1,S2≤10^9, 1≤ Q ≤ 10^5, 1 ≤ qi ≤ L^2, S1≠S2

・特にひっかけもなくdoubleで計算するだけ。

B: Fibonacci Finding (easy)

(制約)1 ≤ T ≤ 1000, 1 ≤ A, B, N ≤ 10^9

・特にひっかけもなく行列累乗で計算するだけ。

C: Cheese and Random Toppings

  • T個のテストケースでそれぞれにおいて整数N, R, M が与えられる
  • このとき、N個のトッピングから R個のトッピングを選ぶ組み合わせの総数を mod M で求めよ

(制約)1 ≤ T ≤ 200, 1 ≤ M ≤ 10^9, 1 ≤ R ≤ N ≤ 10^9, M:square freeかつ各素因数は50を超えない

mod nCrだがMが素数ではないパターン。問題文中にご丁寧にリュカの定理と中国剰余定理のリンクまである。

・蟻本(2版)のP260-263をよく読んで理解する。単位を落とした環論の授業が懐かしまれた。

・コード的には 素進数分解→各素数ごとに mod nCrを求める→中国剰余定理で順次処理してmod M に復元。

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(){
		
		for(int t=0;t<T;t++){
			long n=N[t];
			long r=R[t];
			long m=M[t];
			if(m==1){
				Console.WriteLine(0);
				continue;
			}
			List<long> L=PrimDec(m).Keys.ToList();
			long p=L[0];
			ModComb2.Init(p);
			long ans=ModComb2.Mod_nCr(n,r);
			for(int i=1;i<L.Count;i++){
				ModComb2.Init(L[i]);
				long x=ModComb2.Mod_nCr(n,r);
				ans=ModComb2.CRT(p,ans,L[i],x);
				p*=L[i];
			}
			Console.WriteLine(ans);
		}
	}
	
	int T;
	long[] N,R,M;
	public Sol(){
		T=ri();
		N=new long[T];
		R=new long[T];
		M=new long[T];
		for(int i=0;i<T;i++){
			var d=rla();
			N[i]=d[0];R[i]=d[1];M[i]=d[2];
		}
	}
	
	static int ri(){return int.Parse(Console.ReadLine());}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}

	static Dictionary<long,long> PrimDec(long A){
	 	Dictionary<long,long> D=new Dictionary<long,long>();
	 	if(A==1)return null;
	 	long rem=A;
	 	for(long i=2;i*i<=A;i++){
	 		if(rem%i==0){
	 			long cnt=0;
	 			while(rem%i==0){cnt++;rem/=i;}
	 			D.Add(i,cnt);
	 		}
	 		if(rem==1)break;
	 	}
	 	if(rem!=1)D.Add(rem,1);
	 	return D;
	}
}

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){
		if(n<r || n<0 || r<0)return 0;
		if(n==0||r==n||r==0)return 1;
		long e=0,e1=0,e2=0;
		long num=ModFact(n,ref e);
		long den1=ModFact(r,ref e1);
		long den2=ModFact(n-r,ref e2);
		if(e>e1+e2)return 0;
		long ret= (num*ModInv(den1))%mod;
		ret =(ret*ModInv(den2))%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;
	}
	
	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)%mm;
	}

}

D: Number of zero-xor subsets

  • T個のテストケースでそれぞれにおいて整数Nが与えられる。集合 S={0, 1,…, 2^N − 1}を考える。
  • このとき、Sの部分集合であって、全ての元のXORを取ると0になるような部分集合の総数を mod(1e9+7) で求めよ。なおφ(空集合)は題意を満たすとする。

(制約)1 ≤ T ≤ 10000, 1 ≤ N ≤ 10^18

・各数字について加える・加えないの2^Nの組み合わせを列挙すると、2^kの形の数字を加えた時だけ桁上がりのため組み合わせの数が変わらず、それ以外の時は×2で増えていくことが分かる。

・結局 2^ ( 2 ^N - N ) mod(1e9+7) を計算すればよい。肩の指数は mod(1e9+6) でよい (フェルマーの小定理)。指数累乗を2回やる。

E: A Weird Function

  • T個のテストケースでそれぞれにおいて整数L ,R が与えられる。
  • 閉区間 [L, R]に含まれる数のうち、あるjが存在して j*(j+1)/2 の形で表される数について、その数以下の数であってその数と互いに素なものの個数を考え、その総和を求めよ

(制約)1 ≤ T ≤ 10^5, 1 ≤ L ≤ R ≤ 10^12

オイラーのφ関数を使う。エラトステネスの篩の要領で2e6程度までのφ関数のテーブルを作っておく。

・j*(j+1)/2 のφ関数の値を上記のφ関数テーブルから作成する。 j*(j+1)/2 の偶奇をもとに、 φ(j)×φ(j+1)または φ(j)×φ(j+1)/2 で求まることが分かる。

・あとはj*(j+1)/2 のφ関数の累積和テーブルを作っておき、二分探索で [L,R] に対応する [j,k] を探して和を計算すればよい。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

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

class Sol{
	public void Solve(){
		
		int max=1500010;
		long[] Phi=new long[max];
		for(int i=1;i<max;i++)Phi[i]=i;
		for(int i=2;i<max;i++){
			if(Phi[i]==i){
				for(int j=i;j<max;j+=i){
					Phi[j]/=i;
					Phi[j]*=(i-1);
				}
			}
		}
		long[] Idx=new long[max];
		for(int i=0;i<max;i++){
			Idx[i]=(long)i*(long)(i+1);
			Idx[i]/=2;
		}
		long[] Phi2=new long[max];
		for(int i=1;i<max-1;i++){
			Phi2[i]=Phi[i]*Phi[i+1];
			if(i%4==0 || (i+1)%4==0)Phi2[i]/=2;
		}
		
		long[] sumPhi2=new long[max];
		for(int i=1;i<max;i++){
			sumPhi2[i]=sumPhi2[i-1]+Phi2[i];
		}

		StringBuilder sb=new StringBuilder();
		for(int t=0;t<T;t++){
			int l=0,r=max;
			int lidx=-1;
			while(r-l>1){
				lidx=(r+l)/2;
				if(Idx[lidx]<L[t]){
					l=lidx;
				}else{
					r=lidx;
				}
			}
			while(lidx<max-1 && Idx[lidx]<L[t])lidx++;
			while(lidx>0 && Idx[lidx]>=L[t])lidx--;//not include
			
			int ridx=-1;
			l=0;
			r=max;
			while(r-l>1){
				ridx=(r+l)/2;
				if(Idx[ridx]<R[t]){
					l=ridx;
				}else{
					r=ridx;
				}
			}
			while(ridx<max-1 && Idx[ridx]<R[t])ridx++;
			while(ridx>0 && Idx[ridx]>R[t])ridx--;//include
			sb.Append((sumPhi2[ridx]-sumPhi2[lidx]).ToString()+"\n");
			
		}
		Console.Write(sb.ToString());
	}
	int T;
	long[] L,R;
	public Sol(){
		T=ri();
		L=new long[T];
		R=new long[T];
		for(int i=0;i<T;i++){
			var d=rla();
			L[i]=d[0];R[i]=d[1];
		}
	}

	static int ri(){return int.Parse(Console.ReadLine());}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
}

ここまでは割とすんなりできた。中国剰余定理どこかで使えるとよいな。