{"problem":{"name":"BZOJ2958 序列染色","description":{"content":"给出一个长度为 $n$，由 $\\tt B,W,X$ 三种字符组成的字符串 $S$，你需要把每一个 $\\tt X$ 染成 $\\tt B$ 或 $\\tt W$ 中的一个。 对于给出的 $k$，问由多少种染色方式，使得存在整数 $a,b,c,d$ 满足： - $1\\leq a\\leq b<c\\leq d\\leq n$； - $b=a+k-1$，$d=c+k-1$; - $S_a=S_{a+1}=\\do","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10593"},"statements":[{"statement_type":"Markdown","content":"给出一个长度为 $n$，由 $\\tt B,W,X$ 三种字符组成的字符串 $S$，你需要把每一个 $\\tt X$ 染成 $\\tt B$ 或 $\\tt W$ 中的一个。\n\n对于给出的 $k$，问由多少种染色方式，使得存在整数 $a,b,c,d$ 满足：\n- $1\\leq a\\leq b<c\\leq d\\leq n$；\n- $b=a+k-1$，$d=c+k-1$;\n- $S_a=S_{a+1}=\\dots=S_b=\\tt B$；\n- $S_c=S_{c+1}=\\dots=S_d=\\tt W$；\n\n由于方法可能很多，你只需输出最后的答案对 $10^9+7$ 取模的结果。\n\n## Input\n\n第一行输入两个正整数 $n,k$；\n\n第二行输出一个长度为 $n$ 的字符串 $S$。\n\n## Output\n\n输出一行，包含一个整数，表示答案。\n\n[samples]\n\n## Background\n\n题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。\n\n## Note\n\n对于 $20\\%$ 的数据，$1\\leq n\\leq 20$；\n\n对于 $50\\%$ 的数据，$1\\leq n\\leq 2000$；\n\n对于 $100\\%$ 的数据，$1\\leq n,k\\leq 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10593","tags":["动态规划 DP","O2优化"],"sample_group":[["5 2\nXXXXX","4"]],"created_at":"2026-03-03 11:09:25"}}