3.1测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------
题面大概可以在SuperOj上找到...(P1349~P1351)
------------------------------------------------------------
T1:
首先考虑每个连通块
只要生成一组合法解，通过交换两行两列，旋转就可以得到所有合法解
考虑任选两个元素放在(1,1),(1,2)这两个位置，可以发现接下来每个元素如果行最多是当前行数+1，列最多是当前列数+1，那么每个元素的位置是唯一确定的（这里我是暴力枚举每个位置然后暴力验证的的...嗯..n^5，但是写的机智一点可以做到n^3）
设每个连通块单独搞出来的大小是r[i]*c[i]
因此得到了每个连通块的答案（r[i]!*c[i]!，记为num[i]好了)，另外还可以旋转90度
然后做一个DP：
f(i,j,k)表示已经用了i行j列，前k个连通块的方案数（注意每个连通块占据的空间是可以旋转90度的）
初始f(0,0,0) = 1
然后转移：
f(i,j,k)*num[k+1]*C(n-i,r[k+1])*C(n-j,c[k+1]) -> f(i+r[k+1],j+c[k+1],k+1)
f(i,j,k)*num[k+1]*C(n-i,c[k+1])*C(n-j,r[k+1]) -> f(i+c[k+1],j+r[k+1],k+1)（翻转90度）
最后答案就是f(i,j,连通块个数)
-----------------------------------------------------------
T2:
期望=和/对数
先把每个子树的对数和初始的和求出来
对数是不会变的，那么只需要维护和
首先有一个很naive的想法：对于每个点，考虑他对他父亲的贡献，然后树链剖分一下这个是可以简单地用线段树维护的
那么就想到每次询问的时候枚举他的每个儿子
但是这样是O(n)的
但是每个人只有一个重儿子啊
所以每个人只加上他的重儿子的贡献
那轻儿子呢？在更新贡献的往上跳的时候，因为是轻重链剖分，所以会经过最多不超过log个轻链
所以轻儿子在跳的时候暴力更新就好
------------------------------------------------------------
T3:
我的做法非常麻烦
然而考场上居然有和我一样做法的(Orz syf)...
考场上没调出来（这个做法完全没法调...），后来调出来的，说一下好了：
首先，他的操作是有序的，先搞成无序的，最后乘以k!
首先把原图建立平面直角坐标系
设f(i,j)表示i层，j个颜色时原图第一象限这部分的染法数
g(i,j)表示i层，j个颜色时1,2象限这部分的染法数（那么3,4象限的坑定也是一样的，因为是对称的）
v(i,j)表示i层，j个颜色时1,3象限这部分的染法数
u(i,j)表示i层，j个颜色时1,2,3这部分的染法数
h(i,j)表示i层，j个颜色时总的染法数
其中n层表示输入为n-1时的情况
规定一个说法：如果一个染法，直接把某个象限用一个颜色染了（可以跨过一个象限，比如一次染了1,2象限），就说这个染法是新颖的
设pf(i,j)表示i层，j个颜色时原图第一象限这部分的新颖的染法数
pg(i,j)表示i层，j个颜色时1,2象限这部分的新颖的染法数
pv(i,j)表示i层，j个颜色时1,3象限这部分的新颖的染法数
pu(i,j)表示i层，j个颜色时1,2,3这部分的新颖的染法数
ph(i,j)表示i层，j个颜色时总的新颖的染法数
那么就有转移：
([a]表示a成立的话为1，否则为0）
---（大段公式预警）---
pf(n,k) = [k=0]
f(n,k) = pf(n,k) + ∑(i=0,3)f(n-1,k-i)*(C(3,i)*(C(0,0))
pg(n,k) = [k=1] + [k=2] + 2*(f(n,k-1) - pf(n,k-1))
g(n,k) = pg(n,k) + ∑(i=0,3)g(n-1,k-i) *
(
(C(6,i-0) * C(1,0)) +
(C(4,i-1) * C(1,1))
)
pv(n,k) = [k=2] + 2*(f(n,k-1) - pf(n,k-1))
v(n,k) = pv(n,k) + ∑(i=0,k)(f(n,i)-pf(n,i))*(f(n,k-i)-pf(n,k-i))
pu(n,k) = [k=3] + 2*[k=2] +
(
(2 * (g(n,k-1) - pg(n,k-1))) +
(2 * (f(n,k-1) - pf(n,k-1))) +
(1 * (v(n,k-1) - pv(n,k-1))) +
(3 * (f(n,k-2) - pf(n,k-2)))
)
u(n,k) = pu(n,k) + ∑(i=0,9)u(n-1,k-i) *
(
(C(9,i ) * C(2,0))+
(C(7,i-1) * C(2,1))+
(C(5,i-2) * C(2,2))
)
ph(n,k) = [k=4] + 4*[k=3] + 2*[k=2] +
(
(4 * (u(n,k-1) - pu(n,k-1))) +
(4 * (g(n,k-1) - pg(n,k-1))) +
(4 * (g(n,k-2) - pg(n,k-2))) +
(8 * (f(n,k-2) - pf(n,k-2))) +
(2 * (v(n,k-2) - pv(n,k-2))) +
(4 * (f(n,k-3) - pf(n,k-3)))
)
h(n,k) = ph(n,k) + ∑(i=0,12)h(n-1,k-i) *
(
(C(12,i ) * C(4,0)) +
(C(10,i-1) * C(4,1)) +
(C( 8,i-2) * C(4,2)) +
(C( 6,i-3) * C(4,3)) +
(C( 4,i-4) * C(4,4))
)
边界情况是对于x∈{f,g,v,u,h},若k<0或n<=0则x(k,n)=0,若k=0则x(k,n)=1
对于x∈{pf,pg,pv,pu,ph},若k<=0或n<=0则x(k,n)=0
最后的答案就是h(n+1,k)
主要是难调，其实推出来是比较简单的
一个状态可以由比他小一层的状态转移过来，考虑一下把多少个颜色分给这一层新的三角形，多少个颜色分给上一层，然后新加的这一层只有两种三角形，一种是比较小的，一种是由两个小的组成的，枚举一下是多少个分给小的，多少个分给两个小的组成的就好
然后还要考虑不是由上一层转移过来的染法，其实就是那些直接把整个象限给染了的情况
容斥的话太麻烦了，所以我就想了个简单点的方法：转移的时候命令他不可以把整个象限覆盖完，最后再来一起统计覆盖了整个象限答案，方法就是减掉那些新颖的染法
然后手动枚举一下覆盖了哪几个象限，用一些颜色来覆盖一下这些象限，然后把剩下的颜色分给去掉这些象限之后的情况，然后再统计一下每一种染法有没有旋转或者对称后相同的，有的话一起统计一下
然后把从低层转移过来的答案和覆盖了象限的答案加一加就好了
比较让我震惊的是我竟然调了5个小时左右就把这个算法调出来了...
顺便，这个的复杂度是n*k*k的，瓶颈在于求v(n,k)，可以用FFT优化成n*k*log
------------------------------------------------------------
评论 (0)
