[loj3285]Circus

将奶牛的状态用序列$\{a_{1},a_{2},...,a_{m}\}$来描述，其中$a_{i}$表示第$i$头奶牛的位置（奶牛数量为$m$）

下面，先来考虑对于某个特定的$m$如何处理：

对于一条简单路径，如果路径中（不包括端点）所有点度数均为2且端点的度数均不为2（允许为1），则称该路径为一条"链"，显然树上每一条边都恰属于一条链

对于一条链，假设链上的点（包括端点）构成的集合为$C$，删去$C$中的点后被划分为$A$和$B$两个连通块

记$k=|C|-(n-m)$，若存在$k\ge 0$的链，那么任取一个状态$\{a_{i}\}$并令$S=\{a_{i}\}$（集合），简单分析不难得到若$A,B\not\subseteq S$则$S\cap C\ne \empty$，因此构造如下变换：

若$A\not\subseteq S$，将$S\cap C$中最靠近$A$中（任意一点）的点（显然唯一）移动到$A$中（不关心顺序），同理对$B$做此操作，那么即有$A,B\subseteq S$，进而由此可得$|S\cap C|=k$

根据此变换，每一个状态都与某个$A,B\subseteq S$的状态等价，因此仅考虑这类状态中的等价类数即可

注意到$S\cap C$中的点恒在$C$中且顺序不变，因此这些点的贡献可以看作$k!{m\choose k}$，同时由于这些点使得$A$和$B$中点无法交换，因此又即可以变为两个子问题

具体的，令$C_{A}$和$C_{B}$分别为最靠近$A$和$B$中的$|C|-k$个点，子问题的点集即分别为$A\cup C_{A}$和$B\cup C_{B}$，并且分别要选$|A|$和$|B|$头奶牛，另外编号选择还有${m-k\choose |A|}$的贡献

关于$C_{A}$和$C_{B}$，即将中间的$k$个点都移到另一边，那么就空出了这$|C|-k$个位置

重复此过程，直至不存在$k\ge 0$的链，那么这个子问题中任意两个状态都等价，这可以归纳证明

下面，来简单分析一下此递归过程：

1.递归过程中$n-m$的值不变，且代入可得$|C_{A}|=|C_{B}|=n-m$

2.若$m\le n-2$，也即$|C_{A}|=|C_{B}|\ge 2$，那么注意到链的端点仍存在且度数不变，而除了$C_{A}$和$C_{B}$的末尾外其余点度数也不会变化，从而链的划分形式变化即删除了一条链$C$并加入了$C_{A}$和$C_{B}$这两条链

因此，链只需要初始预处理并找出所有$|C|\ge n-m$的链，假设链长（指$|C|$）依次为$l_{1},l_{2},...,l_{k}$，并且将这些链中的点删除后（保留端点），连通块节点数依次为$a_{1},a_{2},...,a_{k+1}$（显然删除一条链恰好增加一个连通块），那么贡献即
$$
{m\choose a_{i}-(n-m),l_{i}-(n-m)}\prod_{i=1}^{k}(l_{i}-(n-m))!
$$
注意$a_{i}$要包含$C_{A}$和$C_{B}$，计算方式即$(n-m-1)\cdot$参与删除的次数+当前节点数

同时，此时剩下的每一个连通块中不存在$k\ge 0$的链，根据前面的结论任意两个状态等价，也即对答案的贡献为1，因此上述贡献即为答案

对于所有$1\le m\le n-2$，不难发现$\sum k$中每一条链贡献恰为$o(l_{i})$，而由于一条边恰属于一条链因此该值和为$o(n)$，换言之可以暴力计算（指$o(k)$）上述贡献

由此，先将所有链删除，并将其按照$m$从大到小后依次合并，使用并查集维护即可

另外，为了快速找到所有$a_{i}$，可以用一个set维护并查集的根

最终，还有$m\ge n-1$的情况，显然此时答案即为$m!$

时间复杂度为$o(n\log n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define mod 1000000007

 5 #define ll long long

 6 struct Data{

 7     int x,y,len;

 8     bool operator < (const Data &k)const{

 9         return len<k.len;

10     }

11 };

12 vector<int>v[N];

13 vector<Data>L;

14 set<int>S;

15 set<int>::iterator it;

16 int n,rt,x,y,fac[N],inv[N],d[N],f[N],sz[N],Sz[N],ans[N];

17 int find(int k){

18     if (k==f[k])return k;

19     return f[k]=find(f[k]);

20 }

21 int merge(int x,int y){

22     x=find(x),y=find(y);

23     S.erase(y);

24     f[y]=x,sz[x]+=sz[y],Sz[x]+=Sz[y];

25     return x;

26 }

27 int C(int n,int m){

28     return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;

29 }

30 void dfs(int k,int fa){

31     f[k]=fa;

32     if ((fa)&&(d[k]!=2)){

33         int pos=f[k],tot=2;

34         for(;d[pos]==2;pos=f[pos])tot++;

35         L.push_back(Data{k,pos,tot});

36     }

37     for(int i=0;i<v[k].size();i++)

38         if (v[k][i]!=fa)dfs(v[k][i],k);

39 }

40 int main(){

41     fac[0]=inv[0]=inv[1]=1;

42     for(int i=1;i<N;i++)fac[i]=(ll)fac[i-1]*i%mod;

43     for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;

44     for(int i=1;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;

45     scanf("%d",&n);

46     for(int i=1;i<n;i++){

47         scanf("%d%d",&x,&y);

48         d[x]++,d[y]++;

49         v[x].push_back(y);

50         v[y].push_back(x);

51     }

52     for(int i=1;i<=n;i++)

53         if (d[i]!=2)rt=i;

54     dfs(rt,0);

55     sort(L.begin(),L.end());

56     for(int i=1;i<=n;i++){

57         f[i]=i,sz[i]=1,Sz[i]=d[i];

58         if (d[i]!=2)S.insert(i);

59     }

60     for(int i=n-2,j=0;i;i--){

61         while ((j<L.size())&&(L[j].len<n-i)){

62             int k=merge(L[j].x,L[j].y);

63             sz[k]+=L[j].len-2,Sz[k]-=2;

64             j++;

65         }

66         ans[i]=1;

67         int m=i;

68         for(it=S.begin();it!=S.end();it++){

69             int s=sz[(*it)]+(n-i-1)*Sz[(*it)]-(n-i);

70             ans[i]=(ll)ans[i]*C(m,s)%mod;

71             m-=s;

72         }

73         for(int k=j;k<L.size();k++){

74             int l=L[k].len-(n-i);

75             ans[i]=(ll)ans[i]*C(m,l)%mod*fac[l]%mod;

76             m-=l;

77         }

78     }

79     ans[n-1]=fac[n-1],ans[n]=fac[n];

80     for(int i=1;i<=n;i++)printf("%d\n",ans[i]);

81     return 0;

82 }

巴特西

[loj3285]Circus

最新文章

热门文章