偶然遇见：Cayley定理
2024-09-05 02:24:52
看到\(purfer\)序列板子后，想到这个名词在哪见过，于是找到了一个题，还带出一个：
\(T1\).
题目链接：P4430 小猴打架
开始极其懵逼，考虑过大力容斥，但还是失败了，原来是：
Cayley定理(凯莱，反正是个神犇就对了):
\(n\)个节点的带标号的形态不同的无根树有\(n^{n-2}\)个，
再乘上\((n-1)!\)种生成方式即可，
\[ans=(n-1)!×n^{n-2}
\]
\]
时间复杂度\(O(n+logn)\)，你要是会快速阶乘，就可以\(O(logn)\)了。
\(Code\):
#include<iostream>
using namespace std;
const int mod=9999991;
long long quickpow(int a,int b)
{
long long ans=1,base=a;
while(b)
{
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
int n;
long long f;
int main()
{
cin>>n;
f=1;
for(int i=2;i<n;i++)
{
f=f*i%mod;
}
f=f*quickpow(n,n-2)%mod;
cout<<f;
return 0;
}
\(T2\).
题目链接：P4981 父子
一样的，只是考虑\(n\)种无根树，
\[ans=n^{n-1}
\]
\]
复杂度\(O(Tlogn)\)，可以通过本题。
\(Code\):
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
ll quickpow(ll a,ll b)
{
ll ans=1,base=a;
while(b!=0)
{
if(b&1!=0)
{
ans=ans*base%mod;
}
base=base*base%mod;
b>>=1;
}
return ans%mod;
}
int t,n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int s=quickpow(n,n-1)%mod;
printf("%d\n",s);
}
return 0;
}
最新文章
- python 五子棋
- Java基本语法
- 使用即时文件初始化提高SQL Server性能
- IE Firefox Safari 下 通过Div“隐藏”设置Accesskey的submit input
- 敏捷开发系列之旅 第二站（走近XP极限编程）
- laravel资源路由详解
- org.springframework.beans.factory.BeanDefinitionStoreException错误
- APP产品设计及运营时常见的问题
- jQuery（一）
- 《ASP.NET Core In Action》读书笔记系列，这是一个手把手的从零开始的教学系列目录
- C++ 中缀转后缀表达式并求值
- Moco使用简单指导
- Redis防止重複請求鎖功能
- Kotlin语言Web库又添一虎将：Kweb
- 20145321 《网络对抗技术》 Web安全基础实践
- Java实验案例（接口）
- HTTP从入门到入土(3)——TCP三次握手
- js 获取后台数据分页
- django 连接mysql报错
- mysql replace 使用注意，update的时候 删除从表数据