0108模拟赛 无人生还

原题传送门:>Here<

第一问

$prufer$序列乱搞即可,

第二问

我们考虑对基环树进行$prufer$序列的操作:每次找到一个编号最小的叶节点并删除,把它连到的那个点加入序列中。

在基环树上这样做时,最后必会剩下一个环和一个点,如图:

(这个形状看起来不大优美。我们能不能把剩下来的那个叶节点也删掉呢?

我们发现如果这样做的话,会导致一个环上的点被加入$prufer$序列中,导致问题变得辣手。所以我们不将这个点删去。)

设环的大小为$i$,则当前的$prufer$序列长度为$n-i-1$。

我们考虑进行$dp$。

可以发现,一个基环树上的点的位置有三种可能:

  • 不在环上,此时该点在$prufer$序列中的出现次数为$d_i-1$;
  • 在环上但不是连接叶结点的点(如图中的$3$号点),此时出现次数为$d_i-2$;
  • 在环上且是连接叶结点的点,此时出现次数为$d_i-3$;

设$f_{i,j,0/1}$为枚举到前$i$个点,有$j$个点在环上,当前第三种点出现过/没有出现过的方案数。

则可以得到转移方程:

最后答案为

其中${(i-1)!\over 2}$为一个大小为$i$的环的排列方案。

第三问

我们发现每个连通块的编号必定都是连续的。所以一个合法排列必定形如

[第$1$个连通块中的数的排列][第$2$个连通块中的数的排列]$\cdots$[第$m$个连通块中的数的排列]

所以我们只要将每个连通块分开考虑即可。

设$f_i$为合法的长度为$i$的连通块的方案数。

则$f_i=i!-($不合法方案数$)$

一个方案不合法,当且仅当它由多于一个连通块构成。我们枚举其中的第一个连通块的大小,后面部分随便排列,得到转移方程

我们发现这个东西可以分治$NTT$。

当递归到区间$[l,r]​$,中点为$mid​$时:

首先处理左边,然后设

这样$f’_i$需要加上

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <cstdio>
#include <cstring>
#define int long long

void swap(int &a,int &b){
static int t;
t=a;
a=b;
b=t;
}
int type,P,n,d[1000001],G,invg;
long long pow[1000001],inv[1000001],invmul[1000001],f[5001][5001][2];
long long g[200001],h[200001],Lim,L=-1,t1[200001],t2[200001],R[200001],ksm[101][2];
long long qsm(long long a,long long b=P-2){
long long ans=1;
while(b){
if(b&1)(ans*=a)%=P;
(a*=a)%=P;
b>>=1;
}
return ans;
}
namespace get_g{
int may[100001],top=0;
int qsm(int a,int b,int P){
int ans=1;
while(b){
if(b&1)ans=(ans*a)%P;
a=(a*a)%P;
b>>=1;
}
return ans;
}
int get_g(int p){
int x=p-1;
for(int i=2;i*i<=x;++i)
if(!(x%i)){
may[++top]=(p-1)/i;
while(!(x%i)) x/=i;
}
if(x>1)may[++top]=(p-1)/x;

int y;
for(int i=2;;++i){
for(int j=1;y=may[j];++j)
if(qsm(i,y,p)==1) break;
if(!y) return i;
}
}
}
void NTT(int *a,int flag){
for(int i=0;i<Lim;i++)if(i<R[i])swap(a[i],a[R[i]]);
for(int i=1,lg=0;i<Lim;i<<=1,lg++)
for(int j=0,T=ksm[lg][flag];j<Lim;j+=(i<<1))
for(int k=0,t=1;k<i;k++,(t*=T)%=P){
int Nx=a[j+k],Ny=t*a[i+j+k]%P;
a[j+k]=(Nx+Ny)%P;
a[i+j+k]=(Nx+P-Ny)%P;
}
}
void solve(int l,int r){
if(l==r){
g[l]=(pow[l]+P-g[l])%P;
return;
}
int mid=(l+r)>>1;
solve(l,mid);

Lim=1,L=-1;
while(Lim<=(r-l+1))Lim<<=1,++L;
for(int i=0;i<Lim;i++)R[i]=(R[i>>1]>>1)|((i&1)<<L);

for(int i=l;i<=mid;i++)t1[i-l]=g[i];
for(int i=mid-l+1;i<Lim;i++)t1[i]=0;
for(int i=0;i<Lim;i++)t2[i]=pow[i];

// printf("solve: %lld %lld %lld\n",l,mid,r);
// for(int i=0;i<Lim;i++)printf("%lld ",t1[i]);putchar('\n');
// for(int i=0;i<Lim;i++)printf("%lld ",t2[i]);putchar('\n');
//
// printf("%d %d\n",G,invg);

NTT(t1,0);
NTT(t2,0);
for(int i=0;i<Lim;i++)(t1[i]*=t2[i])%=P;
NTT(t1,1);
int inverse=qsm(Lim);
// for(int i=0;i<Lim;i++)printf("%lld ",t1[i]);putchar('\n');
for(int i=0;i<Lim;i++)(t1[i]*=inverse)%=P;


for(int i=mid+1;i<=r;i++)(g[i]+=t1[i-l])%=P;

solve(mid+1,r);
}
signed main(){
scanf("%lld%lld",&type,&P);
scanf("%lld",&n);
pow[0]=inv[0]=inv[1]=invmul[0]=1;
for(int i=1;i<=n;i++)pow[i]=(pow[i-1]*i)%P;
for(int i=2;i<=n;i++)inv[i]=(P-P/i)*inv[P%i]%P;
for(int i=1;i<=n;i++)invmul[i]=(invmul[i-1]*inv[i])%P;
if(type==1){
long long ans=pow[n-2];
for(int i=1;i<=n;i++)scanf("%lld",d+i),(ans*=invmul[d[i]-1])%=P;
printf("%lld",ans);
}
else if(type==2){
for(int i=1;i<=n;i++)scanf("%lld",d+i);
f[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<2;k++){
(f[i][j][k]+=f[i-1][j][k]*invmul[d[i]-1])%=P;
if(d[i]>1&&j)(f[i][j][k]+=f[i-1][j-1][k]*invmul[d[i]-2])%=P;
if(d[i]>2&&k&&j)(f[i][j][k]+=f[i-1][j-1][0]*invmul[d[i]-3])%=P;
}
long long ans=0;
for(int i=3;i<n;i++)(ans+=(f[n][i][1]*pow[n-i-1]%P)*(pow[i-1]*inv[2]%P))%=P;
(ans+=(f[n][n][0]*pow[n-1]%P)*inv[2])%=P;
printf("%lld",ans);
}
else if(type==3){
G=get_g::get_g(P);
invg=qsm(G);
for(int i=1,lg=0;lg<=30;i<<=1,lg++)ksm[lg][0]=qsm(G,(P-1)/(i<<1)),ksm[lg][1]=qsm(invg,(P-1)/(i<<1));
solve(1,n);
int t4,t5,t6;
long long ans=1;
scanf("%lld",&t4);
for(int i=1;i<=t4;i++){
scanf("%lld",&t5);
(ans*=g[t5])%=P;
for(int j=1;j<=t5;j++)scanf("%lld",&t6);
}
printf("%lld",ans);
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×