#P18603. Count Hamiltonian Cycles
Count Hamiltonian Cycles
Count Hamiltonian Cycles
给出长度为 的字符串 ,其中恰有 个 W 和 个 B。依次把字符位置编号为 ,并据此建立无向图:两个位置颜色不同时连一条边,其权值为下标距离 ;同色位置之间没有边。
请统计总边权最小的哈密顿环有多少个,答案对 取模。哈密顿环访问每个顶点恰好一次并回到起点,总权值为环中所有边权之和。
按无向边的集合区分环:仅改变起点或遍历方向不算新环。这里的边权是线性下标之差,不是把字符串绕成圆后的最短距离。
输入格式
第一行是测试用例数 ,。
每组先给出整数 ,;下一行是长度为 的字符串,恰含 个 W 和 个 B。所有用例的 之和不超过 。
输出格式
每组输出一个整数,表示最短哈密顿环的数量模 。
样例输入 1
3
2
WWBB
3
WBWBWB
7
WWWWBWBBWWBBBB
样例输出 1
1
2
62208
样例说明
第一组只有四条边,唯一无向环可沿 遍历。沿相反方向走得到相同的边集,仍只计一次。