20200604模拟-lq

liqing的场

赛况大概是,pb做过B,rose、xgc、dqa会B但xgc、dqa没判些特殊情况,rose会C的log方做法,我和pb写了C的40(虽然我是三方暴力

看一遍题50min,C的40分搞了70min,大概30min写了个B发现比大样例(6个点度为3)答案少1,玩了挺久终于发现有种情况没考虑到,但在度数3里并没有找到漏了啥,就这样自闭到了最后……

「ZJOI2010」贪吃的老鼠

留坑

CF914H Ember and Storm’s Tree Game

题意:求有多少棵$n \le 200$点带标号无根树,满足每个点度数不超过d,且任意不同两点间路径,要么是单峰,要么是单调

求出后,乘上$C_n^2*4$输出

请先思考后再展开

猜测对于一棵合法树而言,$S={x|其他点到x路径单调}$(并不代表x是极值)是个非空点集。

好像不好感性理解,但理性证明不难且有意义:如果$x \notin S$,$\exists y,y到x单峰$。以x为根,除了y所在方向外(方向指来自x为根的哪棵子树),其他方向到x都是单调的,一定可以往y那边跳一步(同时这也证明了,S连通

但S的大小不一定是1。取出其中一个点x,将各个方向按照到x是增还是减分成两类

  1. 如果只有一类且数量至少为2,显然$|S|=1$;

  2. 如果每类都至少两个,显然$|S|=1$;

  3. 如果恰一类的数量为1(包括度为1),往那个方向跳一步到y,显然有$y \in S$且其两类方向都是1个。

换句话说,如果$|S| \ne 1$,一定是形如链状,两个端点度数大于2(恰一类的数量为1),中间的点度数为2(两类方向都是1个)

因此我们可以从两端给每种合法方案计数两次,然后计算情况1、2

只需要做个基础的$O(n^3)$的dp,求出大小为n根度数为d的堆个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n=qread(),D=qread(),mod=qread();
if(!qread()){ write(mod==1 or (D==1 and n!=2)?0:1);return; }//不重要
C[0][0]=1;fo(i,1,n){ C[i][0]=1;fo(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; }
dp[1][0]=f[1]=1;
fo(siz,2,n) fo(d,1,D)
{
fo(lst,1,siz-1) if(f[lst] and dp[siz-lst][d-1])
(dp[siz][d]+=dp[siz-lst][d-1]*f[lst]%mod*C[siz-2][lst-1] )%=mod;
if(d<=D-(siz!=n)) (f[siz]+=dp[siz][d])%=mod;
}
ll ans=(f[n]+mod-dp[n][1])*2%mod;
fo(s,1,n-1) fo(d1,2,D) fo(d2,2,D) if(d1+d2<=D) (ans+=dp[s][d1]*dp[n-s+1][d2])%=mod;
fo(s,1,n-1) fo(d,0,D-1) if(d!=1) (ans+=dp[s][d]*dp[n-s+1][1])%=mod;//*(1/2)*2
write((ans+mod)%mod);

CF848E Days of Floral Colours

题意:2n个点按顺时针递增摆成一个环,现在要两两配对(用颜色表示,但与具体颜色无关)

要求配对的点对,要么距离为n(称这类为nb点对),要么距离为不超过2(距离定义为劣弧间不包括端点的点数+1)

另外,还要求得到的图形,在配对关系上,是中心对称的

以下为一种合法的方案:

img

我们定义一种方案的权值为,去掉nb点对后,剩下连续段长度的乘积(上图为$1*3*1*3=9$)。如果不存在nb点对,或者存在相邻两点都被删除,权值为0。统计合法方案的权值和,对$998244353$取模

请先思考后再展开

只需要考虑一个半圆长啥样,另一侧是对称的。每个nb点对在该半圆会有一个点,记为nb点

考虑把编号最小的nb点放到0号位(下文为方便将半圆的位置编号为$1 \sim n$)来做到唯一计数,则1号、n-2号不是,而n-1号是。

讨论一下1号与-1号间是否连边,如果连了可以看作是与n-1号连边,区别不大

将该点集定好后,得到连续段后再考虑配对方案数。定义一段为至少一个非nb点和一个nb点组成,考虑一个个加入

对于染色这件事可以记录前两个是否已经被匹配,$长度^2$考虑其组合意义就是在每段独立地放两个不同的球,故状态可以用4个0/1表示,复杂度为$O(n)$,完整code

另外说一下,这玩意丢进BM里递推式只有十几,矩乘可以冲n=1e18

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
int F[N];int getF(int x){ return x>=0 and x%2==0?F[x/2]:0;}
int dp[N][4][2][3];//dp(i,放球状态,前两个被匹配,其中第二维=2表示nb点)
void main()
{
F[0]=F[1]=1;fo(i,2,N-1) F[i]=mm(F[i-1]+F[i-2]);
int n=qread(),ans=0;
dp[0][0][1][2]=1;
fo(i,1,n-1) fo(s2,0,3) fo(s3,0,3) if((s2&s3)==0) fo(a,0,1) fo(b,0,2)
{
int X=dp[i-1][s2][a][b];if(!X) continue;
if(a==0) add(dp[i][s2|s3][min(b,1)][1],X);
else
{
if(b==0) add(dp[i][s2|s3][1][1],X);
add(dp[i][s2|s3][min(b,1)][0],X);
if(s3==0 and s2==3) {assert(b!=2);add(dp[i][0][b][2],X);}
}
}
fo(i,0,n-1)
{
ll now;
if((n-i-1)%2==0) now=1ll*dp[i][0][1][2]*(n-i-1)%MOD*(n-i-1)%MOD*getF(n-i-1)%MOD;
else now=1ll*dp[i][0][0][2]*(n-i-1)%MOD*(n-i-1)%MOD*getF(n-i-2)%MOD;
add(ans, now*(n-i)%MOD );
}
mem(dp,0);fo(s,0,3) dp[1][s][1][1]=1;//1连n-1
fo(i,2,n-1) fo(s2,0,3) fo(s3,0,3) if((s2&s3)==0) fo(a,0,1) fo(b,0,2)
{
int X=dp[i-1][s2][a][b];if(!X) continue;
if(a==0) add(dp[i][s2|s3][min(b,1)][1],X);
else
{
if(b==0) add(dp[i][s2|s3][1][1],X);
add(dp[i][s2|s3][min(b,1)][0],X);
if(s3==0 and s2==3) {assert(b!=2);add(dp[i][0][b][2],X);}
}
}
//等价于fo(st,1,n) fo(i,0,n-st),然后ans+=now
fo(i,0,n-1)
{
ll now;
if(i==0) now=1ll*(n-1)*(n-1)%MOD*getF(n-3)%MOD;
else if((n-i-2)%2==0) now=1ll*dp[i][0][1][2]*(n-i-1)%MOD*(n-i-1)%MOD*getF(n-i-2)%MOD;
else now=1ll*dp[i][0][0][2]*(n-i-1)%MOD*(n-i-1)%MOD*getF(n-i-3)%MOD;
add(ans, now*(n-i)%MOD );
}
write(ans);
}

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