結果
| 問題 | No.314 ケンケンパ |
| ユーザー |
 バイト
|
| 提出日時 | 2018-06-15 11:02:10 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 129 ms / 1,000 ms |
| コード長 | 11,716 bytes |
| コンパイル時間 | 2,711 ms |
| コンパイル使用メモリ | 81,244 KB |
| 実行使用メモリ | 74,476 KB |
| 最終ジャッジ日時 | 2024-06-30 14:44:28 |
| 合計ジャッジ時間 | 4,654 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
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;//factorialstatic boolean[] isPrime;static int[] primes;static int N;static long[][] dp;public static void main(String[] args){N = sc.nextInt();//k1,k2,pdp = new long[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 = sumMod(dp[0][N - 1], dp[1][N - 1], dp[2][N - 1]);System.out.println(res);}/*** <h1>指定した値以上の先頭のインデクスを返す</h1>* <p>配列要素が０のときは、０が返る。</p>** @return<b>int</b> ： 探索した値以上で、先頭になるインデクス*/public static long sumMod(long... lar){long sum = 0;for (long l : lar)sum = (sum + l % MOD) % MOD;return sum;}public static 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;}}}