题解：CF288B Polo the Penguin and Houses

zengzidi · 2025-11-26 14:49:32 · 题解

这题很明显可以分成两个部分来求解，分别是编号为 1 到 k 的部分和编号为 k+1 到 n 的部分，最后再乘法原理乘起来。

先看编号为 1 到 k。发现 k 最大只有 8，尝试暴力搜索打表。

::::info[O(m^{m+3}) 的暴搜代码]

void dfs(int x)
{
    if(x>m)
    {
        for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)c[i][j]=0;
        for(int i=1;i<=m;i++)c[i][a[i]]=1;
        for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)for(int l=1;l<=m;l++)if(c[j][i] && c[i][l])c[j][l]=1;
        int t=1;
        for(int i=1;i<=m;i++)if(c[i][1]==0)t=0;
        s+=t;
        s%=mod;
        return;
    }
    for(int i=1;i<=m;i++)
    {
        a[x]=i;
        dfs(x+1);
    }
}

::::

记 s 为这部分的结果，可以发现：

可以发现规律 s=k^{k-1}。

再看第二部分。这部分不可能有数字指向 1 到 k，否则会违反条件 2，所以只能指向 k+1 到 n 共 n-k 个。而这部分共有 n-k 个房屋，每个都可以选 n-k 种数，那最后就有 (n-k)^{n-k} 种情况。

最后把两部分相乘，得到结果为 k^{k-1}(n-k)^{n-k}。

::::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5,mod=1e9+7;
int n,m;
int ksm(int A,int B)
{
    int S=1;
    while(B)
    {
        if(B&1)S*=A,S%=mod;
        A*=A,A%=mod;
        B>>=1;
    }
    return S;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int s=1;
    for(int i=1;i<m;i++)s*=m,s%=mod;
    int k=ksm((n-m)%mod,n-m);
    cout<<s*k%mod;
    return 0;
}

::::