当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
4838：The Patterns
题目描述
对于一个1到n的全排列Q，我们定义Q对应的字符串SQ,其中:
例如对于n=5,Q=32154, SQ=DDUD。
本任务为给定一个仅包含字符’U’与’D’长度为m的模式串P以及一个正整数n，求解1到n的任意全排列中模式串出现次数的期望值。例如某个SQ=UUU,P=UU,则P出现次数为2次。
例如n=3,P=U,则1到n的所有全排列方案对应的模式串P出现次数分别为:
则1到n的任意全排列中模式串出现次数的期望值
E=(2+1+1+1+1+0)/6=1.0
为了避免浮点数精度误差，请输出(E*n!) mod (109 +7)， 其中mod为取模操作，具体定义以及运算规则参见： 链接地址
例如对于n=5,Q=32154, SQ=DDUD。
本任务为给定一个仅包含字符’U’与’D’长度为m的模式串P以及一个正整数n，求解1到n的任意全排列中模式串出现次数的期望值。例如某个SQ=UUU,P=UU,则P出现次数为2次。
例如n=3,P=U,则1到n的所有全排列方案对应的模式串P出现次数分别为:
则1到n的任意全排列中模式串出现次数的期望值
E=(2+1+1+1+1+0)/6=1.0
为了避免浮点数精度误差，请输出(E*n!) mod (109 +7)， 其中mod为取模操作，具体定义以及运算规则参见： 链接地址
输入解释
输入数据第一行为一个整数T（1 <= T <= 3333），表示有 T 组测试数据。
下面T组数据，每组数据第一行包含2个正整数n, m，接下来一行包含一个字符串P(仅包含字符’U’与’D’)
数据规模:
1 <= m <= 1000
m<n<=1000000
下面T组数据，每组数据第一行包含2个正整数n, m，接下来一行包含一个字符串P(仅包含字符’U’与’D’)
数据规模:
1 <= m <= 1000
m<n<=1000000
输出解释
对于第k组数据，第一行输出Case #k:，第二行输出(E * n!) mod (10^9 + 7)。
输入样例
5 4 3 UUU 4 2 UU 10 8 UUUUDDDD 2 1 U 2 1 D
输出样例
Case #1: 1 Case #2: 8 Case #3: 1400 Case #4: 1 Case #5: 1
来自杭电HDUOJ的附加信息
| Recommend | liuyiding |
最后修改于 2020-10-25T23:17:19+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 10000/5000MS(Java/Others) | 65535/65535K(Java/Others) |
登陆或注册以提交代码