本文主要是介绍Codeforces Round #177 (Div. 1) B. Polo the Penguin and Houses (组合数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://codeforces.com/contest/288/problem/B
首先，前面的k个与后面的n-k个是没关系的，后面的n-k个显然是(n-k)^(n-k)，所以只需看前k个，而由于2-k都可以到达1，所以1放1-k都可以，所以这时只研究2-k个。
由于都要到达1，所以2-k必须有1，这时候讨论有多少个1，如果有x个1，则此时是C(k-1,x)，然后再讨论2指向这些1，如果有y个指向这些1,的，在这里先称之为2，这时候有x^y*C(k-1-x,y)个，因为对于这些指向1的，每一个都可以是x个1中的任意一个，然后继续讨论下去。用dfs进行深搜就可以实现这个过程。
代码如下：
#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
int k, C[10][10], dp[10][10];
void init()
{memset(C,0,sizeof(C));int i, j;for(int i=1;i<=7;i++){C[i][1]=i;C[i][i]=1;}for(int i=2;i<=7;i++){for(int j=2;j<i;j++){C[i][j]=C[i-1][j-1]+C[i-1][j];}}for(i=1;i<=7;i++){dp[i][1]=i;for(j=2;j<=7;j++){dp[i][j]=dp[i][j-1]*i;}}
}
LL dfs(int tmp, int last)
{if(tmp==k) return 1;int i;LL ans=0;for(i=1;i<=k-tmp;i++){ans+=C[k-tmp][i]*dp[last][i]*dfs(tmp+i,i);if(ans>=mod) ans%=mod;}return ans;
}
int main()
{int n, i, z;init();LL ans=0;scanf("%d%d",&n,&k);z=n-k;k--;for(i=1;i<=k;i++){ans+=C[k][i]*dfs(i,i);if(ans>=mod) ans%=mod;}//printf("%I64d\n",ans);if(!ans) ans=1;ans=(ans*(k+1))%mod;for(i=0;i<z;i++){ans*=z;ans%=mod;}printf("%d\n",ans);return 0;
}这篇关于Codeforces Round #177 (Div. 1) B. Polo the Penguin and Houses (组合数学)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
