题解：CF288B Polo the Penguin and Houses

wyc0607 · 2025-08-27 15:35:53 · 题解

提醒：建议大家看原题意

不然就会像我一样不知道一个点只能连往外连 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}。

代码：

#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;
}