3.1测试总结

------------------------------------------------------------
题面大概可以在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
------------------------------------------------------------