题解：CF288B Polo the Penguin and Houses

提醒：建议大家看原题意

~~不然就会像我一样不知道一个点只能连往外连 1 条边，也不知道允许自环。~~

思路：

分类讨论，

1

到

k

为第一类，

k+1

到

n

为第二类。

第一类，对于每个属于 $1$ 到 $k$ 的节点：
满足 $1$ 到 $k$ 的节点在一个环里。所以只要保证 $i$ 可以去到在 $1$ 到 $k$ 中除了 $i$ 的另一个点就可以了。有 $k-1$ 种选择。

所以此方案总和为

k ^ {k-1}

。

第二类，对于每个属于 $k+1$ 到 $n$ 的节点：
保证不去到由 $1$ 到 $k$ 构成的环就可以了。有 $n-k$ 种选择。

所以此方案总和为

(n-k) ^ {n-k}

。

所以答案为

k^{k-1}\times(n-k)^{n-k}

。

代码：

CPP

#include<bits/stdc++.h>
#define md 1000000007
#define int long long
using namespace std;
int n,k;
int qpow(int a,int b){
	int ans=1;
	a%=md;
	while(b){
		if(b&1) ans*=a,ans%=md;
		a*=a;
		a%=md;
		b/=2;
	}
	return ans;
}
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	cout<<(qpow(n-k,n-k)*qpow(k,k-1))%md;
}

题解：CF288B Polo the Penguin and Houses

文章操作

提醒：建议大家看原题意

思路：

代码：

相关推荐

评论

题解：CF288B Polo the Penguin and Houses