結果
| 問題 | No.213 素数サイコロと合成数サイコロ (3-Easy) |
| ユーザー |
 ぴろず
|
| 提出日時 | 2015-05-22 23:12:31 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,696 bytes |
| コンパイル時間 | 1,908 ms |
| コンパイル使用メモリ | 77,808 KB |
| 実行使用メモリ | 78,348 KB |
| 最終ジャッジ日時 | 2024-07-06 05:32:48 |
| 合計ジャッジ時間 | 10,299 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
ソースコード
package no213;
import java.util.Scanner;
public class Main {
public static int[] d1 = {2,3,5,7,11,13};
public static int[] d2 = {4,6,8,9,10,12};
public static long MOD = 1000000007;
public static int MAX = 251;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
int p = sc.nextInt();
int c = sc.nextInt();
int[] deme1 = deme(d1,p);
int[] deme2 = deme(d2,c);
int[] deme = new int[MAX];
for(int i=0;i<MAX;i++) {
for(int j=0;j<MAX-i;j++) {
deme[i+j] += deme1[i] * deme2[j];
}
}
// System.out.println("hoge");
long[][] a = new long[MAX][MAX];
for(int i=0;i<MAX-1;i++) {
a[i][i+1] = 1;
}
for(int i=1;i<MAX;i++) {
a[i-1][0] = deme[i];
}
MatrixMod A = new MatrixMod(a);
// System.out.println(A);
long[] x = new long[MAX];
x[0] = 1;
MatrixMod X = MatrixMod.vector(x);
MatrixMod B = A.pow(n).multiply(X);
long ans = 0;
for(int i=0;i<MAX;i++) {
ans = (ans + B.e[i][0]) % MOD;
}
System.out.println(ans);
}
public static int[] deme(int[] d,int num) {
if (num == 0) {
int[] ret = new int[MAX];
ret[0] = 1;
return ret;
}
int[] ret = new int[MAX];
int[] p = new int[num];
LOOP: while(true) {
int sum = 0;
for(int i=0;i<num;i++) {
sum += d[p[i]];
}
ret[sum]++;
for(int i=0;i<num;i++) {
p[i]++;
if (p[i] >= 6) {
if (i == num-1) {
break LOOP;
}
p[i] = 0;
}else{
break;
}
}
for(int i=num-1;i>=1;i--) {
if (p[i] > p[i-1]) {
p[i-1] = p[i];
}
}
}
return ret;
}
}
class MatrixMod {
public static long MOD = Main.MOD;
long[][] e;
int n,m;
public MatrixMod(long[][] e) {
this.e = e;
this.n = e.length;
this.m = e[0].length;
}
public static MatrixMod identity(int n) {
long[][] e = new long[n][n];
for(int i=0;i<n;i++) e[i][i] = 1;
return new MatrixMod(e);
}
public static MatrixMod zero(int n,int m) {
return new MatrixMod(new long[n][m]);
}
public static MatrixMod vector(long[] v) {
long[][] e = new long[v.length][1];
for(int i=0;i<v.length;i++) e[i][0] = v[i];
return new MatrixMod(e);
}
public MatrixMod add(MatrixMod b) {
long[][] c = new long[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
c[i][j] = e[i][j] + b.e[i][j];
if (c[i][j] >= MOD) {
c[i][j] -= MOD;
}
}
}
return new MatrixMod(c);
}
public MatrixMod multiply(long k) {
k = (k%MOD+MOD)%MOD;
long[][] c = new long[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
c[i][j] = e[i][j] * k % MOD;
}
}
return new MatrixMod(c);
}
// public MatrixMod multiply(MatrixMod b) {
// long[][] c = new long[n][b.m];
// for(int i=0;i<n;i++) {
// for(int j=0;j<b.m;j++) {
// for(int k=0;k<m;k++) {
// c[i][j] = (c[i][j] + e[i][k] * b.e[k][j]) % MOD;
// }
// }
// }
// return new MatrixMod(c);
// }
public MatrixMod multiply(MatrixMod b) {
long[][] c = new long[n][b.m];
for(int i=0;i<n;i++) {
for(int k=0;k<m;k++) {
if (e[i][k] == 0) {
continue;
}
for(int j=0;j<b.m;j++) {
c[i][j] = (c[i][j] + e[i][k] * b.e[k][j]) % MOD;
}
}
}
return new MatrixMod(c);
}
public MatrixMod pow(long exp) {
MatrixMod ret = identity(n);
MatrixMod x = this;
while(exp > 0) {
if ((exp & 1) != 0) {
ret = ret.multiply(x);
}
x = x.multiply(x);
exp >>>= 1;
}
return ret;
}
public String toString() {
StringBuilder sb = new StringBuilder();
int n2 = Math.min(100, n);
int m2 = Math.min(100, m);
for(int i=0;i<n2;i++) {
for(int j=0;j<m2;j++) {
if (j > 0) {
sb.append(' ');
}
sb.append(e[i][j]);
}
sb.append('\n');
}
return sb.toString();
}
}