{"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\n对于每组数据，第一行一个字符串 $S$，第二行一个整数 $m$。\n\n## Output\n\n对于每组数据，输出 $i=0,1,\\dots,|S|$ 时的答案，每个占一行。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，保证 $1\\leq T\\leq 5$，$1\\leq |S| \\leq 15$，$1\\leq m\\leq 1000$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10614","tags":["字符串","O2优化","有限状态自动机","DP 套 DP"],"sample_group":[["1\nGTC\n10","1\n22783\n528340\n497452"]],"created_at":"2026-03-03 11:09:25"}}