A. Bear and Friendship Condition
并查集：每个集合的个数，如果集合若是有向强连通分量，则集合内边数必须满足n*(n-1)/2
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int f[N],n,m,ans,sz[N];
int r_find(int r)
{
if(r==f[r])
return f[r];
f[r]=r_find(f[r]);
sz[r]=sz[f[r]];
return f[r];
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i,sz[i]=1;
for(int i=1;i<=m;i++)
{
int x,y;cin>>x>>y;
if(x>y) swap(x,y);
int fx=r_find(x),fy=r_find(y);
if(fx==fy)
continue;
f[fx]=fy;
sz[fx]+=sz[fy];
sz[fy]=sz[fx];
}
int flag=0;
for(int i=1;i<=n;i++)
{
if(f[i]==i)
{
// cout<<sz[i]<<endl;
ans+=(1LL*sz[i]*(sz[i]-1))/2;
}
}
if(ans!=m)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
return 0;
}
P6870 [COCI2019-2020#5] Zapina
c[i][j] ：预处理出所有要用到的组合式，使用递推公式
dp思路：
设 f(i,j)f(i,j) 表示前 ii 个人分配前 jj 道题且至少已经有一个人开心的方案数。
考虑转移：
使 i 开心：随便給他 i 道，剩下 j?i 道随便分給剩下的 i?1 个人。 方案数：f[i][j]=c[j][i]*fastpow(i-1,j-i)%mod;
使 i 不开心：随便給他 k 道，剩下 j?k 道給 i?1 个人并使这 i?1 个人中有人开心。 方案数：f[i][j]=(f[i][j]+c[j][k]*f[i-1][j-k])%mod;
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
const int mod=1e9+7;
int n,m,c[N][N],f[N][N];
int fastpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int a) //求逆元
{
return fastpow(a,mod-2)%mod;
}
/*
int C(int n,int m) //C(n,m)
{
return ((fac[n]*getinv(fac[m])%mod)*(getinv(fac[n-m])%mod))%mod;
}*/
signed main()
{
cin>>n;
for(int i=0;i<=n;i++) //C(n,m)的递推公式
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
f[1][1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(j>=i)
f[i][j]=c[j][i]*fastpow(i-1,j-i)%mod;
for(int k=0;k<=j;k++)
{
if(i!=k)
f[i][j]=(f[i][j]+c[j][k]*f[i-1][j-k])%mod;
}
}
cout<<f[n][n]<<endl;
return 0;
}
