http://codeforces.com/contest/568/problem/B
题意:题意还挺绕的，其实就是说:要你求出一个图，要求保证其中有至少一个点不连任何边，然后其他连边的点构成的每个联通块都必须构成完全连通图
思路:f[i][j]代表i个点，构成j个联通块的方案数
f[i][j]=f[i][j-1]*j(代表与其中一个联通块合并)+f[i-1][j-1](代表新开一个联通块)
然后答案是Σc[n][i]*f[i][j]
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#define ll long long
const ll Mod=;
ll f[][],c[][];
int n;
ll Pow(ll x,ll y){
ll res=;
while (y){
if (y&) res=(res*x)%Mod;
y/=;
x=(x*x)%Mod;
}
return res;
}
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int main(){
n=read();
ll ans=;
for (int i=;i<=n;i++) c[i][]=c[i][i]=;
for (int i=;i<=n;i++)
for (int j=;j<i;j++)
c[i][j]=(c[i-][j]+c[i-][j-])%Mod;
f[][]=;
for (int i=;i<=n;i++)
for (int j=;j<=i;j++)
f[i][j]=((1LL*f[i-][j]*j)%Mod+f[i-][j-])%Mod;
for (int i=;i<n;i++)
for (int j=;j<=i;j++)
ans=(ans+f[i][j]*c[n][i])%Mod;
printf("%lld\n",ans);
return ;
}