一开始有N个互不认识的同学,每回合交友都只有两个不认识的人成为好朋友,每回合结束后两个认识的好朋友也会认识并成为好朋友,经过N-1回合交友后所有人都会互相认识,求解有多少种交友过程。
比如当N=3时,就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的交友过程。
输入N,
输出方案数mod 9999991。
一开始有N个互不认识的同学,每回合交友都只有两个不认识的人成为好朋友,每回合结束后两个认识的好朋友也会认识并成为好朋友,经过N-1回合交友后所有人都会互相认识,求解有多少种交友过程。
比如当N=3时,就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的交友过程。
输入N,
输出方案数mod 9999991。
用c或者c++
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
int main()
{
int n;
ll ans=1;
scanf("%d",&n);
for(int i=1;i<n;i++)
ans=(ans*i)%9999991;
int a=n;
for(int i=1;i<n-1;i++)
ans=ans*a%9999991;
ans=ans%9999991;
printf("%lld",ans);
return 0;
}