結果
| 問題 | No.314 ケンケンパ |
| ユーザー |
 バイト
|
| 提出日時 | 2018-06-15 10:51:51 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 82 ms / 1,000 ms |
| コード長 | 11,553 bytes |
| コンパイル時間 | 2,345 ms |
| コンパイル使用メモリ | 78,764 KB |
| 実行使用メモリ | 61,556 KB |
| 最終ジャッジ日時 | 2023-09-13 04:32:10 |
| 合計ジャッジ時間 | 4,605 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 82 ms
61,252 KB |
| testcase_01 | AC | 42 ms
49,444 KB |
| testcase_02 | AC | 41 ms
49,468 KB |
| testcase_03 | AC | 40 ms
49,548 KB |
| testcase_04 | AC | 40 ms
49,512 KB |
| testcase_05 | AC | 40 ms
49,420 KB |
| testcase_06 | AC | 40 ms
49,456 KB |
| testcase_07 | AC | 41 ms
49,400 KB |
| testcase_08 | AC | 41 ms
49,520 KB |
| testcase_09 | AC | 41 ms
49,460 KB |
| testcase_10 | AC | 42 ms
49,572 KB |
| testcase_11 | AC | 41 ms
49,416 KB |
| testcase_12 | AC | 41 ms
49,784 KB |
| testcase_13 | AC | 41 ms
49,452 KB |
| testcase_14 | AC | 44 ms
49,456 KB |
| testcase_15 | AC | 45 ms
49,412 KB |
| testcase_16 | AC | 47 ms
49,688 KB |
| testcase_17 | AC | 54 ms
49,416 KB |
| testcase_18 | AC | 75 ms
57,836 KB |
| testcase_19 | AC | 81 ms
61,556 KB |
ソースコード
import java.io.*;
import java.util.*;
/**
* @author baito
*/
public class Main
{
static StringBuilder sb = new StringBuilder();
static FastScanner sc = new FastScanner(System.in);
static int INF = 10000;
static int MOD = 1000000007;
static int[] y4 = {0, 1, 0, -1};
static int[] x4 = {1, 0, -1, 0};
static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
static long[] F;//factorial
static boolean[] isPrime;
static int[] primes;
static int N;
static int[][] dp;
public static void main(String[] args)
{
N = sc.nextInt();
//k1,k2,p
dp = new int[3][N];
dp[0][0] = 1;
dp[1][0] = 0;
dp[2][0] = 0;
//long,INFを忘れるな
for (int i = 1; i < N; i++)
{
dp[0][i] = dp[2][i-1] % MOD;
dp[1][i] = dp[0][i-1] % MOD;
dp[2][i] = dp[0][i-1] % MOD + dp[1][i-1] % MOD;
}
long res = (((long) dp[0][N-1] + dp[1][N-1])%MOD + dp[2][N-1])%MOD;
System.out.println(res);
}
/**
* <h1>指定した値以上の先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @return<b>int</b> ： 探索した値以上で、先頭になるインデクス
*/
public static final int lowerBound(final int[] arr, final int value)
{
int low = 0;
int high = arr.length;
int mid;
while (low < high)
{
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] < value)
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
/**
* <h1>指定した値より大きい先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @return<b>int</b> ： 探索した値より上で、先頭になるインデクス
*/
public static final int upperBound(final int[] arr, final int value)
{
int low = 0;
int high = arr.length;
int mid;
while (low < high)
{
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] <= value)
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
//次の順列に書き換える、最大値ならfalseを返す
public static boolean nextPermutation(int A[])
{
int len = A.length;
int pos = len - 2;
for (; pos >= 0; pos--)
{
if (A[pos] < A[pos + 1]) break;
}
if (pos == -1) return false;
//posより大きい最小の数を二分探索
int ok = pos + 1;
int ng = len;
while (Math.abs(ng - ok) > 1)
{
int mid = (ok + ng) / 2;
if (A[mid] > A[pos]) ok = mid;
else ng = mid;
}
swap(A, pos, ok);
reverse(A, pos + 1, len - 1);
return true;
}
//次の順列に書き換える、最小値ならfalseを返す
public static boolean prevPermutation(int A[])
{
int len = A.length;
int pos = len - 2;
for (; pos >= 0; pos--)
{
if (A[pos] > A[pos + 1]) break;
}
if (pos == -1) return false;
//posより小さい最大の数を二分探索
int ok = pos + 1;
int ng = len;
while (Math.abs(ng - ok) > 1)
{
int mid = (ok + ng) / 2;
if (A[mid] < A[pos]) ok = mid;
else ng = mid;
}
swap(A, pos, ok);
reverse(A, pos + 1, len - 1);
return true;
}
//↓nCrをmod計算するために必要。 ***factorial(N)を呼ぶ必要がある***
static long ncr(int n, int r)
{
factorial(n);
return F[n] / (F[n - r] * F[r]);
}
static long modNcr(int n, int r)
{
long result = F[n];
result = result * modInv(F[n - r]) % MOD;
result = result * modInv(F[r]) % MOD;
return result;
}
static long modInv(long n)
{
return modPow(n, MOD - 2);
}
static void factorial(int n)
{
F = new long[n + 1];
F[0] = F[1] = 1;
for (int i = 2; i <= n; i++)
{
F[i] = (F[i - 1] * i) % MOD;
}
}
static long modPow(long x, long n)
{
long res = 1L;
while (n > 0)
{
if ((n & 1) == 1)
{
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return res;
}
//↑nCrをmod計算するために必要
static int gcd(int n, int r)
{
return r == 0 ? n : gcd(r, n % r);
}
static long gcd(long n, long r)
{
return r == 0 ? n : gcd(r, n % r);
}
static <T> void swap(T[] x, int i, int j)
{
T t = x[i];
x[i] = x[j];
x[j] = t;
}
static void swap(int[] x, int i, int j)
{
int t = x[i];
x[i] = x[j];
x[j] = t;
}
public static void reverse(int[] x)
{
int l = 0;
int r = x.length - 1;
while (l < r)
{
int temp = x[l];
x[l] = x[r];
x[r] = temp;
l++;
r--;
}
}
public static void reverse(int[] x, int s, int e)
{
int l = s;
int r = e;
while (l < r)
{
int temp = x[l];
x[l] = x[r];
x[r] = temp;
l++;
r--;
}
}
static int length(int a)
{
int cou = 0;
while (a != 0)
{
a /= 10;
cou++;
}
return cou;
}
static int length(long a)
{
int cou = 0;
while (a != 0)
{
a /= 10;
cou++;
}
return cou;
}
static int countC2(char[][] a, char c)
{
int co = 0;
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a[0].length; j++)
if (a[i][j] == c) co++;
return co;
}
static void fill(int[][] a, int v)
{
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a[0].length; j++)
a[i][j] = v;
}
static int max(int a, int b, int c)
{
return Math.max(a, Math.max(b, c));
}
static int abs(int a)
{
return Math.abs(a);
}
static class FastScanner
{
private BufferedReader reader = null;
private StringTokenizer tokenizer = null;
public FastScanner(InputStream in)
{
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
public String next()
{
if (tokenizer == null || !tokenizer.hasMoreTokens())
{
try
{
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e)
{
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
/*public String nextChar(){
return (char)next()[0];
}*/
public String nextLine()
{
if (tokenizer == null || !tokenizer.hasMoreTokens())
{
try
{
return reader.readLine();
} catch (IOException e)
{
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
public long nextLong()
{
return Long.parseLong(next());
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public int[] nextIntArray(int n)
{
int[] a = new int[n];
for (int i = 0; i < n; i++)
{
a[i] = nextInt();
}
return a;
}
public int[][] nextIntArray2(int h, int w)
{
int[][] a = new int[h][w];
for (int hi = 0; hi < h; hi++)
{
for (int wi = 0; wi < w; wi++)
{
a[hi][wi] = nextInt();
}
}
return a;
}
public int[] nextIntArray21(int n, int scalar)
{
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt() * scalar + nextInt();
return a;
}
public Integer[] nextIntegerArray(int n)
{
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++)
{
a[i] = nextInt();
}
return a;
}
public char[] nextCharArray(int n)
{
char[] a = next().toCharArray();
return a;
}
public char[][] nextCharArray2(int h, int w)
{
char[][] a = new char[h][w];
for (int i = 0; i < h; i++)
{
a[i] = next().toCharArray();
}
return a;
}
//スペースが入っている場合
public char[][] nextCharArray2s(int h, int w)
{
char[][] a = new char[h][w];
for (int i = 0; i < h; i++)
{
a[i] = nextLine().replace(" ", "").toCharArray();
}
return a;
}
public char[][] nextWrapCharArray2(int h, int w, char c)
{
char[][] a = new char[h + 2][w + 2];
//char c = '*';
int i;
for (i = 0; i < w + 2; i++)
a[0][i] = c;
for (i = 1; i < h + 1; i++)
{
a[i] = (c + next() + c).toCharArray();
}
for (i = 0; i < w + 2; i++)
a[h + 1][i] = c;
return a;
}
//スペースが入ってる時用
public char[][] nextWrapCharArray2s(int h, int w, char c)
{
char[][] a = new char[h + 2][w + 2];
//char c = '*';
int i;
for (i = 0; i < w + 2; i++)
a[0][i] = c;
for (i = 1; i < h + 1; i++)
{
a[i] = (c + nextLine().replace(" ", "") + c).toCharArray();
}
for (i = 0; i < w + 2; i++)
a[h + 1][i] = c;
return a;
}
public long[] nextLongArray(int n)
{
long[] a = new long[n];
for (int i = 0; i < n; i++)
{
a[i] = nextLong();
}
return a;
}
public long[][] nextLongArray2(int h, int w)
{
long[][] a = new long[h][w];
for (int hi = 0; hi < h; hi++)
{
for (int wi = 0; wi < h; wi++)
{
a[h][w] = nextLong();
}
}
return a;
}
}
}