fork download
copy 
  1. import java.io.IOException;
  2. import java.io.OutputStreamWriter;
  3. import java.io.BufferedWriter;
  4. import java.util.InputMismatchException;
  5. import java.io.OutputStream;
  6. import java.io.PrintWriter;
  7. import java.util.NoSuchElementException;
  8. import java.io.Writer;
  9. import java.math.BigInteger;
  10. import java.io.InputStream;
  11.  
  12. /**
  13.  * Built using CHelper plug-in
  14.  * Actual solution is at the top
  15.  */
  16. public class Main {
  17. 	public static void main(String[] args) {
  18. 		InputStream inputStream = System.in;
  19. 		OutputStream outputStream = System.out;
  20. 		InputReader in = new InputReader(inputStream);
  21. 		OutputWriter out = new OutputWriter(outputStream);
  22. 		TaskD solver = new TaskD();
  23. 		solver.solve(1, in, out);
  24. 		out.close();
  25. 	}
  26. }
  27.  
  28. class TaskD {
  29.     final static int mod = (int)1e9 + 7;
  30.  
  31.     public void solve(int testNumber, InputReader in, OutputWriter out) {
  32.         int n = in.readInt();
  33.         int[][] dp = new int[n][];
  34.         int[][] sums = new int[n][];
  35.         dp[0] = new int[1];
  36.         sums[0] = new int[1];
  37.         dp[0][0] = 1;
  38.         sums[0][0] = 1;
  39.         for (int i = 1; i < n; i++) {
  40.             dp[i] = new int[i + 1];
  41.             sums[i] = new int[i + 1];
  42.             if (i % 2 == 0) {
  43.                 for (int last = 0; last <= i; last++) {
  44.                     int add = getSum(sums[i - 1], last, i - 1);
  45.                     dp[i][last] += add;
  46.                     dp[i][last] %= mod;
  47.                 }
  48.             } else {
  49.                 for (int last = 0; last <= i; last++) {
  50.                     int add = getSum(sums[i - 1], 0, last - 1);
  51.                     dp[i][last] += add;
  52.                     dp[i][last] %= mod;
  53.                 }
  54.             }
  55.             for (int last = 0; last <= i; last++) {
  56.                 if (last > 0) {
  57.                     sums[i][last] += sums[i][last - 1];
  58.                     sums[i][last] %= mod;
  59.                 }
  60.                 sums[i][last] += dp[i][last];
  61.                 sums[i][last] %= mod;
  62.             }
  63.         }
  64.         int ans = 0;
  65.         for (int last = 0; last < n; last++) {
  66.             ans += dp[n - 1][last];
  67.             ans %= mod;
  68.         }
  69.         out.printLine(ans);
  70.     }
  71.  
  72.     private int getSum(int[] sum, int L, int R) {
  73.         if (L > R) {
  74.             return 0;
  75.         }
  76.         int res = sum[R];
  77.         if (L > 0) {
  78.             res -= sum[L - 1];
  79.             res += mod;
  80.             res %= mod;
  81.         }
  82.         return res;
  83.     }
  84. }
  85.  
  86. class InputReader {
  87.  
  88.     private InputStream stream;
  89. 	private byte[] buf = new byte[1024];
  90. 	private int curChar;
  91. 	private int numChars;
  92. 	private SpaceCharFilter filter;
  93.  
  94. 	public InputReader(InputStream stream) {
  95. 		this.stream = stream;
  96. 	}
  97.  
  98. 	public int read() {
  99. 		if (numChars == -1)
  100. 			throw new InputMismatchException();
  101. 		if (curChar >= numChars) {
  102. 			curChar = 0;
  103. 			try {
  104. 				numChars = stream.read(buf);
  105. 			} catch (IOException e) {
  106. 				throw new InputMismatchException();
  107. 			}
  108. 			if (numChars <= 0)
  109. 				return -1;
  110. 		}
  111. 		return buf[curChar++];
  112. 	}
  113.  
  114.     public int readInt() {
  115. 		int c = read();
  116. 		while (isSpaceChar(c))
  117. 			c = read();
  118. 		int sgn = 1;
  119. 		if (c == '-') {
  120. 			sgn = -1;
  121. 			c = read();
  122. 		}
  123. 		int res = 0;
  124. 		do {
  125. 			if (c < '0' || c > '9')
  126. 				throw new InputMismatchException();
  127. 			res *= 10;
  128. 			res += c - '0';
  129. 			c = read();
  130. 		} while (!isSpaceChar(c));
  131. 		return res * sgn;
  132. 	}
  133.  
  134.     public boolean isSpaceChar(int c) {
  135. 		if (filter != null)
  136. 			return filter.isSpaceChar(c);
  137. 		return isWhitespace(c);
  138. 	}
  139.  
  140. 	public static boolean isWhitespace(int c) {
  141. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  142. 	}
  143.  
  144.     public interface SpaceCharFilter {
  145. 		public boolean isSpaceChar(int ch);
  146. 	}
  147. }
  148.  
  149. class OutputWriter {
  150. 	private final PrintWriter writer;
  151.  
  152. 	public OutputWriter(OutputStream outputStream) {
  153. 		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  154. 	}
  155.  
  156. 	public OutputWriter(Writer writer) {
  157. 		this.writer = new PrintWriter(writer);
  158. 	}
  159.  
  160.     public void close() {
  161. 		writer.close();
  162. 	}
  163.  
  164.     public void printLine(int i) {
  165. 		writer.println(i);
  166. 	}
  167. }
  168.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
4
stdout
copy 
5
https://ideone.com/2pj1eO
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!