LOJ6044 共

Posted by yjjr's blog on January 1, 2018

标签:数论,组合数学

题目

题目传送门

这里写图片描述

分析

2018年的第一道题,RP++

5分——手玩样例puts(“12”); 20分——F[i][j]表示一棵i+j个节点的有根树,其中i个节点深度为奇数,j个节点深度为偶数的方案数,然后不停枚举除根以外,编号最小的点所在子树情况进行转移 40分——用S(N,M)表示左边N个点,右边M个点的完全二分图生成树个数,答案就是S(K,N-K)C(N-1,K-1) 100分——观察法:$S(N,M)=N^{M-1}M^{N-1}$,套用40分的公式得出答案,本题复杂度瓶颈在于求组合数

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define dep(i,a,b) for(ll i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll n,k,p,ans;
ll inv(ll a){
	return a==1?1:(ll)(p-p/a)*inv(p%a)%p;
}

ll C(ll n,ll m){
	if(m<0||n<m)return 0;if(m>n-m)m=n-m;
	ll up=1,down=1;
	rep(i,0,m-1){up=up*(n-i)%p;down=down*(i+1)%p;}
	return up*inv(down)%p;
}
ll qpow(ll a,ll b){
	ll re=1;
	while(b){
		if(b&1)re=(re*a)%p;
		a=a*a%p;
		b>>=1;
	}
	return re%p;
}
int main()
{
	n=read(),k=read(),p=read();
	ans=C(n-1,k-1)%p;ans=ans*qpow(k,n-k-1)%p;ans=qpow(n-k,k-1)*ans%p;
	cout<<ans<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr