首页 > 代码库 > Aizu 2164 CSUOJ 1436 Revenge of the Round Table

Aizu 2164 CSUOJ 1436 Revenge of the Round Table

2024-07-06 02:58:37   225人阅读


dp套一个burnside的壳子
核心还是dp
dp[i]表示有i个循环节时的染色方案数
注意在dp的时候，不需要考虑重构的问题
因为burnside会解决重构的问题
dpA[i][j]表示以A开头，长度为i，结尾为j个A的合法方案数
dpB[i][j]表示以B开头，长度为i，结尾为j个A的合法方案数
接下来我们用dpA,dpB来计算dp[i]
显然对于所有的dpB[i][1~k]都是满足dp[i]的
因为它表示以B开头，以A结尾的染色方案，且结尾没有超过k个
另外还有一部分就是以A开头的了
假设我们在整个串的最前面放p个A(p<=k)
在这串A后面放以B开头，以A结尾的串（也就是dpB表示的串）
那么结尾的A不能超过k-p个
也就是说，当我在整个串的最前面放p个A时，所有的
dpB[i-p][0],dpB[i-p][1],dpB[i-p][2]............dpB[i-p][k-p]
都是合法的，这里可以直接用一个前缀和来处理。
计算出dp[i]之后，剩下的就是套一个burnside的壳子了
注意n<=k的时候的处理，最后结果要+2

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 1010;
 7 const int mod = 1000003;
 8 typedef long long LL;
 9 int dpA[maxn][maxn],dpB[maxn][maxn],dp[maxn];
10 int n,k;
11 LL ans,all;
12 
13 void DP(){
14     memset(dpA,0,sizeof(dpA));
15     memset(dpB,0,sizeof(dpB));
16     memset(dp,0,sizeof(dp));
17     int asum = 1,bsum = 0;
18     if(k >= n){
19         k = n-1;
20         all = 2;
21     }
22     dpA[1][1] = 1;
23     dpB[1][1] = 0;
24 
25     for(int i = 2;i <= n;i++){
26         dpA[i][1] = bsum;
27         dpB[i][1] = asum;
28         swap(asum,bsum);
29         for(int j = 2;j <= min(n,k);j++){
30             dpA[i][j] = dpA[i-1][j-1];
31             asum = (asum+dpA[i][j])%mod;
32             dpB[i][j] = dpB[i-1][j-1];
33             bsum = (bsum+dpB[i][j])%mod;
34         }
35     }
36 
37     for(int i = 1;i <= n;i++){
38         for(int j = 1;j <= min(n,k);j++){
39             dp[i] += dpB[i][j];
40             dp[i] %= mod;
41         }
42     }
43 
44     for(int i = 1;i <= n;i++){
45         for(int j = 1;j < k;j++){
46             dpB[i][j+1] += dpB[i][j];
47             dpB[i][j+1] %= mod;
48         }
49     }
50 
51     for(int i = 1;i <= n;i++){
52         for(int p = 1;p <= min(i,k);p++){
53             dp[i] += dpB[i-p][k-p];
54             dp[i] %= mod;
55         }
56     }
57 }
58 
59 int gcd(int a,int b){
60     return b == 0 ? a : gcd(b,a%b);
61 }
62 
63 LL pow_mod(LL a,LL n){
64     LL ret = 1;
65     while(n){
66         if(n&1) ret = ret*a%mod;
67         n >>= 1;
68         a = a*a%mod;
69     }
70     return ret;
71 }
72 
73 int main()
74 {
75     while(scanf("%d%d",&n,&k) == 2){
76         ans = 0,all = 0;
77         DP();
78         for(int i = 0;i < n;i++){
79             ans += 2*dp[gcd(i,n)];
80             ans %= mod;
81         }
82         ans = ans*pow_mod(n,mod-2)%mod;
83         printf("%lld\n",(ans+all)%mod);
84     }
85     return 0;
86 }
View Code

 


联系
我们