結果
問題 | No.336 門松列列 |
ユーザー |
![]() |
提出日時 | 2016-01-15 23:52:11 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 1,502 bytes |
コンパイル時間 | 2,108 ms |
コンパイル使用メモリ | 76,912 KB |
実行使用メモリ | 57,668 KB |
最終ジャッジ日時 | 2024-06-12 01:11:05 |
合計ジャッジ時間 | 4,234 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 |
ソースコード
package no336;import java.util.Scanner;public class Main {//https://oeis.org/A001250//https://en.wikipedia.org/wiki/Alternating_permutation//http://mathworld.wolfram.com/EntringerNumber.htmlpublic static long MOD = 1000000007;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();if (n == 1 || n == 2) {System.out.println(0);return;}int[][] e = new int[n+1][n+1];e[0][0] = 1;for(int i=1;i<=n;i++) {for(int j=1;j<=i;j++) {e[i][j] = e[i][j-1] + e[i-1][i-j];if (e[i][j] >= MOD) {e[i][j] -= MOD;}}}System.out.println(e[n][n] * 2 % MOD);}public static int solveNaive(int n) {int[] p = new int[n];for(int i=0;i<n;i++) {p[i] = i+1;}int ans = 0;LOOP: do {for(int i=0;i<n-2;i++) {if (!isKadomatsuSequence(p[i], p[i+1], p[i+2])) {continue LOOP;}}ans++;}while(nextPermutation(p));return ans;}public static boolean isKadomatsuSequence(long a,long b,long c) {if (a == b || b == c) {return false;}return b < a && b < c || b > a && b > c;}static boolean nextPermutation(int[] p) {for(int a=p.length-2;a>=0;--a) {if(p[a]<p[a+1]) {for(int b=p.length-1;;--b) {if(p[b]>p[a]) {int t = p[a];p[a] = p[b];p[b] = t;for(++a, b=p.length-1;a<b;++a,--b) {t = p[a];p[a] = p[b];p[b] = t;}return true;}}}}return false;}}