BZOJ1815: [Shoi2006]color 有色图

### Description
![图片标题](https://www.lydsy.com/JudgeOnline/images/1815.jpg)
Input
输入三个整数N,M,P 1< = N <= 53 1< = M < = 1000 N< P < = 10^ 9
### Output
即总数模P后的余数
### Sample Input

3 2 97

### Sample Output

论文里写的很好，觉得自己也写不出比它好的题解了qwq。
https://wenku.baidu.com/view/284648d7c1c708a1284a4425.html

```
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 60;
 
int tot[N + 5], cnt, L[N + 5], ans, rn, m, mod;
LL step[N + 5], sinv[N + 5], inv[N + 5];
 
void Add(int &x, const int &b) {
    x += b; if(x >= mod) x -= mod;
}
 
LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
void pre(int n) {
    step[0] = 1, sinv[0] = 1, inv[0] = 1;
    for(register int i = 1; i <= n; ++i) {
        step[i] = step[i - 1] * i % mod;
        inv[i] = fpow(i, mod - 2);
    }
    sinv[n] = fpow(step[n], mod - 2);
    for(register int i = n - 1; i >= 1; --i)
        sinv[i] = sinv[i + 1] * (i + 1) % mod;
}
 
void dfs(int n) {
    if(n == 0) {
        int st = 0;
        //计算边置换的环个数
        for(register int i = 1; i <= cnt; ++i)
            st += L[i] / 2; 
        for(register int i = 1; i <= cnt; ++i)
            for(register int j = i + 1; j <= cnt; ++j)
                st += gcd(L[i], L[j]); 
        //计算同类置换个数 
        int nowst = step[rn];
        for(register int i = 1; i <= cnt; ++i)
            nowst = nowst * inv[L[i]] % mod;
        for(register int i = 1; i <= rn; ++i)
            nowst = nowst * sinv[tot[i]] % mod;
        Add(ans, fpow(m, st) * nowst % mod);
        return ;
    }
    for(register int i = 1; i <= L[cnt] && i <= n; ++i) {
        L[++cnt] = i, ++tot[i];
        dfs(n - i);
        --cnt, --tot[i];
    }
}
 
 
int main() {
    scanf("%d%d%d", &rn, &m, &mod);
    if(rn == 0) {
        printf("0");
        return 0;
    }
    pre(rn), L[0] = rn;
    dfs(rn);
    printf("%d", ans * sinv[rn] % mod);
    return 0;
}

```

Rockdu's Blog

导航

最近发表

大佬们的友链