Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
BZOJ1815: [Shoi2006]color 有色图
? 解题记录 ?
? BZOJ ?
? 群论 ?
2019-01-05 11:59:18
524
0
0
rockdu
? 解题记录 ?
? BZOJ ?
? 群论 ?
### 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 4 论文里写的很好,觉得自己也写不出比它好的题解了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; } ```
上一篇:
洛谷4363 [九省联考2018]一双木棋chess
下一篇:
BZOJ5091: [Lydsy1711月赛]摘苹果
0
赞
524 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册