20191024模拟-rose

rose的场

loj2351「JOI 2018 Final」毒蛇越狱

请先思考后再展开

首先一个$2^{cnt?}$的做法就是直接枚举每个?的值

然后你会发现你还可以想到一个$2^{cnt1}$的做法,就是先预处理出高维前缀和,将问号看做1,0看做0,枚举1的子集作为0去询问高维前缀和(求子集和),做一个简单容斥,式子我就不写了;然后很明显类似地求补集和,枚举0的子集去作为1,问号看做0,1看做1,就能得到一个$2^{cnt0}$的做法

复杂度均衡一下,就是$q*2^{n/3}$,code

uoj46【清华集训2014】玄学

这里

AGC008E Next or Nextnext

请先思考后再展开

强如rose才能想出这种高端性质题吧,确实是一道合适的防ak题

对于排列p,一个自然的想法是考虑其p图$i \to p_i$,那么题目就是问有多少个这样的带标号p图,满足i跳1步或2步后到ai

然而这样不好挖掘性质,考虑怎么更好地利用给出的a去理解,对于p图的限制,换而言之就是用a图$i \to a_i$去统计p图

注意,我们只关心图的结构(显然p图是若干个环,a图是基环树森林),然后我们知道是带标号的,但具体标号并不重要

首先,考虑p图中一个环可以存在多少个对应的a图(以下为题解的图,左边为p图,重标号成$p_i=i+1$):

第一种是直接连,完全相同

第二种是奇环上所有人跳两步才连到a,可见a图奇环(除了一元环)可以选择形成一个不同构的环

第三种是偶环上所有人跳两步才连到a,可见a图两个相同的环可以合并,且合并后不参与其他合并

第四种是变成一个基环树,注意这个基环树如果是合法的,一定满足环上节点最多2入边,非环节点最多1入边也就是只挂着链

于是我们回到a图中,分开处理环和基环树(因为之间不能合并);对于环,奇环可以选择变换形态,如果合并一定是两个大小相同的(显然方案数为大小),将相同大小的一起处理,用这种环数量的复杂度做个简单dp即可

问题是如何求出每个基环树对应多少个p图(基环树间显然不能合并),你发现我们只需要考虑怎么把链贴上去,就能统计出所有形态了,然后最多有两种情况,即考虑链的第一条边是跳几步(右边是p图,每个点都是连向左边,黑色表示如何到达ai):

我们用边数考虑长度、距离;设这条链的长度为l1,这个链头与下个链头的距离为l2,当$l1=l2$时只能选择第一种,因为第二种会导致下一条链与其a距离>2;当$l1>l2$无解

综上所述,$O(n)$

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
int a[N],cnt[N],in[N],len[N],tim[N];
vc<int> cir[N];int id;bool oncir[N];
int tl[N];ll f[N];
void main()
{
int n=qread();fo(i,1,n) a[i]=qread(),in[a[i]]++;
fo(rt,1,n) if(!in[rt])//处理基环树
{
int now=rt;tim[rt]=rt;while(!tim[a[now]]) now=a[now],tim[now]=rt;//a[now]为链头
if(tim[a[now]]==rt)//新找到的基环树
{
cir[++id].PB(now);for(int i=now;a[i]!=now;i=a[i]) cir[id].PB(a[i]);
for(auto x:cir[id]) oncir[x]=1;
}
else if(!oncir[a[now]] or tl[a[now]]) {puts("0");return;}//非法的基环树
int ln=0;for(int i=rt;i!=a[now];i=a[i]) ln++;tl[a[now]]=ln;
}
fo(rt,1,n) if(!tim[rt])//环
{
int ln=0;for(int i=rt;!tim[i];i=a[i]) ln++,tim[i]=rt;
cnt[ln]++;
}
ll ans=1;
fo(siz,1,n)//环
{
int m=cnt[siz];f[0]=1;f[1]=(1+(siz&1 and siz>1));
fo(i,2,m) f[i]=(f[i-1]*f[1]+f[i-2]*siz*(i-1))%MOD;
ans=ans*f[m]%MOD;
}
fo(i,1,id)//基环树
{
int m=sz(cir[i]);reverse(all(cir[i]));
cir[i].resize(m+m);
fo(j,m,m+m-1) cir[i][j]=cir[i][j-m];
int lstpos=INF;
fd(j,m+m-1,0) if(tl[cir[i][j]]>0)
{
if(j<m)
{
int l1=tl[cir[i][j]],l2=lstpos-j;
if(l1>l2)ans=0; else ans=ans*(1+(l1!=l2))%MOD;
}
lstpos=j;
}
}
write(ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f3401588.html
转载请注明出处,谢谢!