Advertisement
Guest User

RCC Elim D

a guest
Jun 8th, 2014
425
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.47 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class saw_bm {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.  
  8.     void solve() {
  9.         int n = in.nextInt();
  10.         final int MOD = (int) 1e9 + 7;
  11.         int[] dp1 = new int[n + 1];
  12.         dp1[n] = 1;
  13.         int[] dp2 = new int[n + 1];
  14.         for (int i = 0; i < n; i++) {
  15.             Arrays.fill(dp2, 0);
  16.             int total = n - i;
  17.             if (i % 2 == 0) {
  18.                 int numberOfWays = 0;
  19.                 for (int cur = total - 1; cur >= 0; cur--) {
  20.                     numberOfWays += dp1[cur + 1];
  21.                     if (numberOfWays >= MOD)
  22.                         numberOfWays -= MOD;
  23.                     dp2[cur] += numberOfWays;
  24.                     if (dp2[cur] >= MOD)
  25.                         dp2[cur] -= MOD;
  26.                 }
  27.             } else {
  28.                 int numberOfWays = 0;
  29.                 for (int cur = 0; cur< total; cur++) {
  30.                     numberOfWays += dp1[cur];
  31.                     if (numberOfWays >= MOD)
  32.                         numberOfWays -= MOD;
  33.                     dp2[cur] += numberOfWays;
  34.                     if (dp2[cur] >= MOD)
  35.                         dp2[cur] -= MOD;
  36.                 }
  37.             }
  38.             int[] tmp = dp1;
  39.             dp1 = dp2;
  40.             dp2 = tmp;
  41.         }
  42.         long res = 0;
  43.         for (int i = 0; i <= n; i++) {
  44.             res += dp1[i];
  45.         }
  46.         out.println(res % MOD);
  47.     }
  48.  
  49.     void run() {
  50.         try {
  51.             in = new FastScanner(new File("saw.in"));
  52.             out = new PrintWriter(new File("saw.out"));
  53.  
  54.             solve();
  55.  
  56.             out.close();
  57.         } catch (FileNotFoundException e) {
  58.             e.printStackTrace();
  59.         }
  60.     }
  61.  
  62.     void runIO() {
  63.  
  64.         in = new FastScanner(System.in);
  65.         out = new PrintWriter(System.out);
  66.  
  67.         solve();
  68.  
  69.         out.close();
  70.     }
  71.  
  72.     class FastScanner {
  73.         BufferedReader br;
  74.         StringTokenizer st;
  75.  
  76.         public FastScanner(File f) {
  77.             try {
  78.                 br = new BufferedReader(new FileReader(f));
  79.             } catch (FileNotFoundException e) {
  80.                 e.printStackTrace();
  81.             }
  82.         }
  83.  
  84.         public FastScanner(InputStream f) {
  85.             br = new BufferedReader(new InputStreamReader(f));
  86.         }
  87.  
  88.         String next() {
  89.             while (st == null || !st.hasMoreTokens()) {
  90.                 String s = null;
  91.                 try {
  92.                     s = br.readLine();
  93.                 } catch (IOException e) {
  94.                     e.printStackTrace();
  95.                 }
  96.                 if (s == null)
  97.                     return null;
  98.                 st = new StringTokenizer(s);
  99.             }
  100.             return st.nextToken();
  101.         }
  102.  
  103.         boolean hasMoreTokens() {
  104.             while (st == null || !st.hasMoreTokens()) {
  105.                 String s = null;
  106.                 try {
  107.                     s = br.readLine();
  108.                 } catch (IOException e) {
  109.                     e.printStackTrace();
  110.                 }
  111.                 if (s == null)
  112.                     return false;
  113.                 st = new StringTokenizer(s);
  114.             }
  115.             return true;
  116.         }
  117.  
  118.         int nextInt() {
  119.             return Integer.parseInt(next());
  120.         }
  121.  
  122.         long nextLong() {
  123.             return Long.parseLong(next());
  124.         }
  125.     }
  126.  
  127.     public static void main(String[] args) {
  128.         new saw_bm().runIO();
  129.     }
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement