fork download
copy 
  1. import java.util.*
  2.  
  3. fun main(args: Array<String>) {
  4.     val sc = Scanner(System.`in`)
  5.         if (!sc.hasNextInt()) return
  6.             val n = sc.nextInt()
  7.                 val s = sc.next()
  8.                     val m = s.length
  9.                         val mod = 1_000_000_007
  10.  
  11.                             val nextState = Array(m + 1) { IntArray(2) } // 0 = '(', 1 = ')'
  12.                                 for (i in 0..m) {
  13.                                         for (charIdx in 0..1) {
  14.                                                     val c = if (charIdx == 0) '(' else ')'
  15.                                                                 var curStr = s.substring(0, Math.min(i, m)) + c
  16.                                                                             for (len in curStr.length downTo 0) {
  17.                                                                                             if (len <= m) {
  18.                                                                                                                 if (s.startsWith(curStr.substring(curStr.length - len))) {
  19.                                                                                                                                         nextState[i][charIdx] = len
  20.                                                                                                                                                                 break
  21.                                                                                                                                                                                     }
  22.                                                                                                                                                                                                     }
  23.                                                                                                                                                                                                                 }
  24.                                                                                                                                                                                                                         }
  25.                                                                                                                                                                                                                             }
  26.  
  27.                                                                                                                                                                                                                                 val dp = Array(2 * n + 1) { Array(n + 1) { IntArray(m + 1) } }
  28.                                                                                                                                                                                                                                     dp[0][0][0] = 1
  29.  
  30.                                                                                                                                                                                                                                         for (i in 0 until 2 * n) {
  31.                                                                                                                                                                                                                                                 for (j in 0..n) {
  32.                                                                                                                                                                                                                                                             for (k in 0..m) {
  33.                                                                                                                                                                                                                                                                             if (dp[i][j][k] == 0) continue
  34.  
  35.                                                                                                                                                                                                                                                                                                             // Try '('
  36.                                                                                                                                                                                                                                                                                                                             if (j + 1 <= n) {
  37.                                                                                                                                                                                                                                                                                                                                                 val nk = if (k == m) m else nextState[k][0]
  38.                                                                                                                                                                                                                                                                                                                                                                     dp[i + 1][j + 1][nk] = (dp[i + 1][j + 1][nk] + dp[i][j][k]) % mod
  39.                                                                                                                                                                                                                                                                                                                                                                                     }
  40.  
  41.                                                                                                                                                                                                                                                                                                                                                                                                                     // Try ')'
  42.                                                                                                                                                                                                                                                                                                                                                                                                                                     if (j - 1 >= 0) {
  43.                                                                                                                                                                                                                                                                                                                                                                                                                                                         val nk = if (k == m) m else nextState[k][1]
  44.                                                                                                                                                                                                                                                                                                                                                                                                                                                                             dp[i + 1][j - 1][nk] = (dp[i + 1][j - 1][nk] + dp[i][j][k]) % mod
  45.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             }
  46.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         }
  47.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 }
  48.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     }
  49.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         println(dp[2 * n][0][m])
  50.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         }
Success #stdin #stdout 0.19s 42784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u0ScdR
language:
Kotlin (kotlin 1.3.21)
created:
12 hours 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!