BZOJ3864 Hero meet devil

Luogu

IDLGP10614

Time3000ms

Memory512MB

DifficultyP6

字符串O2优化有限状态自动机DP 套 DP

给定一个字符集为 `ACGT` 的字符串 $S$。定义 $\text{LCS}(S,T)$ 为两个字符串 $S,T$ 的最长公共子序列。对于每个 $0\leq i \leq |S|$，求有多少个长度为 $m$，字符集 `ACGT` 的字符串 $T$，满足 $|\text{LCS}(S,T)|=i$，答案对 $10^9+7$ 取模。 ## Input 第一行一个整数 $T$ 表示数据组数。对于每组数据，第一行一个字符串 $S$，第二行一个整数 $m$。 ## Output 对于每组数据，输出 $i=0,1,\dots,|S|$ 时的答案，每个占一行。 [samples] ## Note 对于 $100\%$ 的数据，保证 $1\leq T\leq 5$，$1\leq |S| \leq 15$，$1\leq m\leq 1000$。

Samples

Input #1

1
GTC
10

Output #1

API Response (JSON)

{
  "problem": {
    "name": "BZOJ3864 Hero meet devil",
    "description": {
      "content": "给定一个字符集为 `ACGT` 的字符串 $S$。定义 $\\text{LCS}(S,T)$ 为两个字符串 $S,T$ 的最长公共子序列。 对于每个 $0\\leq i \\leq |S|$，求有多少个长度为 $m$，字符集 `ACGT` 的字符串 $T$，满足 $|\\text{LCS}(S,T)|=i$，答案对 $10^9+7$ 取模。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10614"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个字符集为 `ACGT` 的字符串 $S$。定义 $\\text{LCS}(S,T)$ 为两个字符串 $S,T$ 的最长公共子序列。\n\n对于每个 $0\\leq i \\leq |S|$，求有多少个长度为 $m$，字符集 `ACGT` 的字符串 $T$，满足 $|\\text{LCS}(S,T)|=i$，答案对 $10^9+7$ 取模。\n\n## Input\n\n第一行一个整数 $T$ 表示数据组数。\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments