AOJ 2164 Revenge of the Round Table
圆桌基情:有男女共n人入座一个圆桌,若连续k个以上同性坐在一起就会搞基。求不搞基的坐法种数?
4.1更加复杂的数学问题
计数
大的思路还是Burnside引理,难点在于怎么计算染色种数。
在循环节长度i和k固定的时候,循环节的个数应该是gcd(i,n)。下面考虑循环节个数为i时的方案数dp[i]。
记男为A,女为B,定义:
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的合法方案数
这两种串的dp递推是很简单的,递推a的时候就用b的前缀和作为dp_a[i][1],因为在以B开头的串前面放一个A就是以A开头的串了。同理递推B。
下面就看这两种串如何组合以满足dp[i]。
以B开头
对于所有的dp_b[i][1~k]都是满足dp[i],因为首尾不同,将任意两个串组合后不会超出k。
以A开头
假设串前面有p个A,那么结尾的A不能超过k-p个,即dp_b[i-p][0~k-p]都是合法的,这恰好是一个dp_b的前缀和。
最后一个Burnside引理就能求出来,在实现的时候,发现了一个线性求逆元的方法:
可以用来高效地求Burnside引理的分子除以分母对MOD的模,于是有如下代码:
#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define MAX_N 1000 + 16 #define MOD 1000003 typedef long long LL; int 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的合法方案数 dp[MAX_N]; // dp[i]表示有i个循环节时的染色方案数 int n, k; LL ans, all; LL inv[MAX_N]; // 线性求乘法逆元 a×b ≡ 1 (mod m) void init_inverse() { inv[1] = 1; for (int i = 2; i < MAX_N; i++) inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD; } void solve() { memset(dp_a, 0, sizeof(dp_a)); memset(dp_b, 0, sizeof(dp_b)); memset(dp, 0, sizeof(dp)); int a_sum = 1, 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 swap(a_sum, b_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]; // 在结尾加上B 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 <= min(i, k); p++) { dp[i] += dp_b[i - p][k - p]; dp[i] %= MOD; } } } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif init_inverse(); while (~scanf("%d%d", &n, &k))// for AOJ use while (scanf("%d%d", &n, &k) , n) { ans = 0, all = 0; solve(); for (int i = 0; i < n; i++) { ans += 2 * dp[gcd(i, n)]; // 交换AB ans %= MOD; } ans = ans * inv[n] % MOD; printf("%lld\n", (ans + all) % MOD); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub////////////////////////////////// /************************************************************** Problem: 1436 User: hankcs Language: C++ Result: Accepted Time:76 ms Memory:9560 kb ****************************************************************/
我提交的时候恰逢AOJ宕机,所以提交到了CSUOJ上,后者对输入的处理有所不同,敬请注意。
Reference
http://blog.csdn.net/u013625492/article/details/46787157
知识共享署名-非商业性使用-相同方式共享:码农场 » AOJ 2164 Revenge of the Round Table 题解《挑战程序设计竞赛》
这个MOD改用n*1000003就可以了,正好不会溢出,最后结果再%1000003,就OK了
请问Hanlp训练分词模型的语料格式为什么是分好词的?就是单纯的一文章行吗?
有监督,不行