题解：CF288B Polo the Penguin and Houses

这题很明显可以分成两个部分来求解，分别是编号为

1

到

k

的部分和编号为

k+1

到

n

的部分，最后再乘法原理乘起来。

先看编号为

1

到

k

。发现

k

最大只有

8

，尝试暴力搜索打表。

O(m^{m+3})

的暴搜代码

CPP

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

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

$k=1$ 时， $s=1$ 。
$k=2$ 时， $s=2$ 。
$k=3$ 时， $s=9$ 。
$k=4$ 时， $s=64$ 。
$k=5$ 时， $s=625$ 。
$k=6$ 时， $s=7776$ 。
$k=7$ 时， $s=117649$ 。
$k=8$ 时， $s=2097152$ 。

可以发现规律

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}

。

code

CPP

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

题解：CF288B Polo the Penguin and Houses

文章操作

相关推荐

评论

题解：CF288B Polo the Penguin and Houses