結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー 37zigen37zigen
提出日時 2016-05-07 16:57:35
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,032 ms / 3,000 ms
コード長 3,761 bytes
コンパイル時間 2,800 ms
コンパイル使用メモリ 81,684 KB
実行使用メモリ 47,548 KB
最終ジャッジ日時 2024-04-15 13:37:29
合計ジャッジ時間 4,947 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 503 ms
47,548 KB
testcase_01 AC 1,032 ms
46,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		new Main().solve();
	}
	final long mod=1_000_000_000+7;
	void solve(){
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		int p=sc.nextInt();
		int c=sc.nextInt();
		//まず、さいころをP+C個振って和がK個になるパターン数をDPで数える。
		long[][] k=new long[p+c+1][13*(p+c)+1];
		k[0][0]=1;
		int[] prime={2,3,5,7,11,13};
		int[] composite={4,6,8,9,10,12};
		for(int l=0;l<6;l++){
			for(int i=0;i<p;i++){
				for(int j=0;j<k[0].length;j++){
					if(k[i][j]>0){
						k[i+1][j+prime[l]]+=k[i][j];
						k[i+1][j+prime[l]]%=mod;
					}
				}
			}
		}
		for(int l=0;l<6;l++){
			for(int i=0;i<c;i++){
				for(int j=0;j<k[0].length;j++){
					if(k[p+i][j]>0){
						k[p+i+1][j+composite[l]]+=k[p+i][j];
						k[p+i+1][j+composite[l]]%=mod;
					}
				}
			}
		}

		//コンパニオン行列
		/**
		 *0 1 0 0 0 0 0 0 0 0 0 0 0
		 *0 0 1 0 0 0 0 0 0 0 0 0 0
		 *0 0 0 1 0 0 0 0 0 0 0 0 0
		 *0 0 0 0 1 0 0 0 0 0 0 0 0
		 *0 0 0 0 0 1 0 0 0 0 0 0 0
		 *0 0 0 0 0 0 1 0 0 0 0 0 0
		 *0 0 0 0 0 0 0 1 0 0 0 0 0
		 *0 0 0 0 0 0 0 0 1 0 0 0 0
		 *0 0 0 0 0 0 0 0 0 1 0 0 0
		 *0 0 0 0 0 0 0 0 0 0 1 0 0
		 *0 0 0 0 0 0 0 0 0 0 0 1 0
		 *0 0 0 0 0 0 0 0 0 0 0 0 1
		 *0 1 0 0 0 1 0 1 0 1 1 0 0
		 *
		 */
		int n_k=k[0].length-1;
		long[][] A=new long[n_k][n_k];
		for(int i=0;i<n_k-1;i++)A[i][i+1]=1;
		for(int i=0;i<n_k;i++){
			A[n_k-1][i]=k[p+c][n_k-i];
		}

		//a[1]~a[n_k]を用意
		long[][] a=new long[n_k][1];

		for(int i=1;i<k[0].length;i++){
			//iはサイコロの目の和
			for(int j=0;j>-k[0].length;j--){
				//-jから出発した場合
				if(i+j>=1){
					a[i+j-1][0]+=k[p+c][i];
					a[i+j-1][0]%=mod;
				}
			}
		}
		for(int i=0;i<a.length;i++){
			for(int j=i-1;j>=0;j--){
				a[i][0]+=(k[p+c][i-j]*a[j][0])%mod;
				a[i][0]%=mod;
			}
		}
		//			showMt(a);
//		long[][] T1=companionP2(A);
//		T1=companionP2(T1);
//		showMt(T1);
//		long[][] T2=MtPrd(A, A);
//		T2=MtPrd(T2,T2);
//		showMt(T2);
//		boolean f=isSame(T1,T2);
//		System.out.println(f);
		a=companionMtPow(n-1,A,a);
//				showMt(A);
		System.out.println(a[0][0]%mod);
	}
	//コンパニオン行列の繰り返し二乗法
	long[][] companionMtPow(long n,long[][] A,long[][] v){
		long[][] B=new long[A.length][A.length];
		for(int i=0;i<A.length;i++)
			for(int j=0;j<A.length;j++)
				B[i][j]=A[i][j];
		while(n>0){
			if((n&1)==1)
				v=MtPrd(B,v);
			B=companionP2(B,A);
			n>>=1;
		}
		return v;
	}
	//コンパニオン行列の二乗
	//originalは元のコンパニオン行列
	
	long[][] companionP2(long[][] A,long[][] original){
		int n=A.length;
		long[][] C=new long[n][n];
		//0行目のみ愚直に計算
		long[][] a=new long[1][n];
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				a[0][j]+=(A[0][k]*A[k][j])%mod;
				a[0][j]%=mod;
			}
			a[0][j]%=mod;
			C[0][j]=a[0][j];
		}
		for(int i=1;i<n;i++){
			a=MtPrd(a,original);
			for(int j=0;j<n;j++)
				C[i][j]=a[0][j];
		}
		return C;
	}
	long[][] MtPrd(long[][] A,long[][] B){
		long[][] C=new long[A.length][B[0].length];
		for(int i=0;i<A.length;i++){
			for(int j=0;j<B[0].length;j++){
				for(int k=0;k<A[0].length;k++){
					C[i][j]+=(A[i][k]*B[k][j])%mod;
					C[i][j]%=mod;
				}
			}
		}
		return C;
	}
	//行列を表示
	void showMt(long[][] A){
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				System.out.print(A[i][j]+" ");
			}
			System.out.println();
		}
	}
	void tr(Object...o){System.out.println(Arrays.deepToString(o));}
	boolean isSame(long[][] A,long[][] B){
		int n=A.length;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(A[i][j]!=B[i][j])return false;
			}
		}
		return true;
	}
}
0