首页 > 代码库 > UVA 10843 - Anne's game(Cayley定理)
UVA 10843 - Anne's game(Cayley定理)
UVA 10843 - Anne‘s game
题目链接
题意:题意说得挺绕的,其实本质上就是求n个点,可以接连出多少种不同的生成树
思路:这是Caylay定理,网上能找到证明,结果为nn?2,然后利用快速幂去求解。
代码:
#include <stdio.h>
#include <string.h>
const int long long MOD = 2000000011;
int t;
long long n;
long long pow_mod(long long n, long long k) {
if (k == 0) return 1;
if (k == 1) return n;
return (pow_mod(n * n % MOD, k / 2) * (k&1 ? n : 1)) % MOD;
}
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
scanf("%lld", &n);
printf("Case #%d: %lld\n", ++cas, n == 1 ? 1 : pow_mod(n, n - 2));
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。