挑战程序竞赛系列（46）：4.1Polya 计数定理（2）
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
- AOJ 2164: Revenge of the Round Table
AOJ 2164: Revenge of the Round Table
思路： 首先能想到的是Polya计数，但是此题的trick在于还需要控制A或B不能连续出现的次数。
始终注意Polya计数定理是找寻状态在【置换】前后不变的个数，所以此题依旧如此，对于n个人，对应编号为0…n - 1，那么t = gcd(i,n)能够得到t条轨迹（单独的循环节），可以参考《挑战》P303，很有意思，对应的t = i，于是我们可以尝试【枚举】0，1，…，i - 1个位置合法分配情况。
接着参考博文： http://www.hankcs.com/program/algorithm/aoj-2164-revenge-of-the-round-table.html
所以有了:
代码语言：javascript复制dp_a[MAX_N][MAX_N], // dp_a[i][j]表示以A开头，长度为i，结尾为j个A的合法方案数
dp_b[MAX_N][MAX_N], // dp_b[i][j]表示以B开头，长度为i，结尾为j个A的合法方案数因为第 i - 1个位置 和 第 i 个位置是否合法，需要看dp[i]本身，可以理解为：（0, 1, …, i - 1）和（i, i 1, …, 2 * i - 1）的每个状态是一致的。
比如：
代码语言：javascript复制n = 8, i = 4, t = gcd(4, 8) = 4
0 1 2 3 | 4 5 6 7
A A B B A A B B
对于最终dp[i]的提取，我们需要{0,1,2,3}的结尾信息和{4,5,6,7}的开头信息。
而根据polya定理{4,5,6,7}实际就是{0,1,2,3}
所以在排列组合时，只需要考虑{0,1,2,3},但我们需要定义结尾状态和开头状态。- 此处还需要注意一些细节，比如k≥nk ge n的情况，此时可以有全部的A或B参加，有两种额外的情况，接着把k变成n-1，又变成了基础情况。
- 递推式dp_a[i][j] 和 dp_b[i][j] 有一个小技巧，如下：
dp_a[i][1] = b_sum; // 以B开头以A结尾的串开头放一个A
dp_b[i][1] = a_sum; // 以A开头以A结尾的串开头放一个B
A开头的为前一轮的以b开头的所有情况，同理B开头的为前一轮的以a开头的所有情况。
为什么？
对于第一种情况：
以B开头，在开头加个A之后，再来个逆置，就是以A开头，结尾为1个A的所有情况。
对于第二种情况：
以A开头，在结尾加个B之后，再来个逆置，就是以B开头，结尾为1个A的所有情况。这里再给出一个求逆元的方法，开个脑洞，利用了一些数学性质，想是想不到，但很好理解。
逆元是因为ans在寻环节累加前就取模了，所以不能单纯的除以置换的个数。
代码如下：
代码语言：javascript复制import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/A2164.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MOD = 1000003;
static final int MAX_N = 1000 16;
long[] inv = new long[MAX_N];
int[][] dp_a = new int[MAX_N][MAX_N];
int[][] dp_b = new int[MAX_N][MAX_N];
int[] dp = new int[MAX_N];
void init_inverse() {
inv[1] = 1;
for (int i = 2; i < MAX_N; i) {
inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
}
}
class GCD {
int d;
int x;
int y;
public GCD(int d, int x, int y) {
this.d = d;
this.x = x;
this.y = y;
}
}
GCD extgcd(int a, int b) {
if (b == 0) {
return new GCD(a, 1, 0);
} else {
GCD p = extgcd(b, a % b);
GCD ans = new GCD(0, 0, 0);
ans.d = p.d;
ans.x = p.y;
ans.y = p.x - (a / b) * p.y;
return ans;
}
}
long mod_inverse(int a, int m) {
GCD p = extgcd(a, m);
if (p.d != 1)
return -1;
return (p.x % m m) % m;
}
void DP() {
dp_a = new int[MAX_N][MAX_N];
dp_b = new int[MAX_N][MAX_N];
dp = new int[MAX_N];
int a_sum = 1;
int b_sum = 0;
if (K >= N) {
K = N - 1;
all = 2;
}
dp_a[1][1] = 1;
dp_b[1][1] = 0;
for (int i = 2; i <= N; i ) {
dp_a[i][1] = b_sum; // 以B开头以A结尾的串开头放一个A
dp_b[i][1] = a_sum; // 以A开头以A结尾的串开头放一个B
int sum = a_sum b_sum;
a_sum = sum - a_sum;
b_sum = sum - a_sum;
for (int j = 2; j <= K; j ) {
dp_a[i][j] = dp_a[i - 1][j - 1]; // 在结尾加上A
a_sum = (a_sum dp_a[i][j]) % MOD;
dp_b[i][j] = dp_b[i - 1][j - 1]; // 在结尾加上A
b_sum = (b_sum dp_b[i][j]) % MOD;
}
}
// 对于所有的dp_b[i][1~k]都是满足dp[i]，因为首尾不同，将任意两个串组合后不会超出k
for (int i = 1; i <= N; i ) {
for (int j = 1; j <= K; j ) {
dp[i] = dp_b[i][j];
dp[i] %= MOD;
}
}
// 对于以A开头的串，先将dp_b前缀和求出来
for (int i = 1; i <= N; i ) {
for (int j = 1; j < K; j ) {
dp_b[i][j 1] = dp_b[i][j];
dp_b[i][j 1] %= MOD;
}
}
// 考虑前面有p个A，那么结尾的A不能超过k-p个，即dp_b[i-p][0~k-p]都是合法的
for (int i = 1; i <= N; i ) {
for (int p = 1; p <= Math.min(i, K); p ) {
dp[i] = dp_b[i - p][K - p];
dp[i] %= MOD;
}
}
}
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int N;
int K;
long ans;
long all;
void solve() {
init_inverse();
while (true) {
N = ni();
K = ni();
if (N K == 0)
break;
ans = 0;
all = 0;
DP();
for (int i = 0; i < N; i) {
ans = 2 * dp[gcd(i, N)];
ans %= MOD;
}
ans = (ans * inv[N]) % MOD;
out.println(ans all);
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = !System.getProperty("user.dir").equals("F:\java_workspace\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj) {
System.out.println("[" (System.currentTimeMillis() - s) "ms]");
}
}
public boolean more() {
return in.hasNext();
}
public int ni() {
return in.nextInt();
}
public long nl() {
return in.nextLong();
}
public double nd() {
return in.nextDouble();
}
public String ns() {
return in.nextString();
}
public char nc() {
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext() {
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar() {
if (next == null) {
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}
这DP真不好想，学习了~
