AGC022F Checkers

· · 题解

Tags: Tree，dp，计数

不是，为什么这么抽象的题赛时过的人比 D 多啊？？
对着某篇错的题解瞪了一天，真服了。

考虑转化题意。我们令一次 A 关于 B 对称的操作对应为在一个图上将点 B 向点 A 连一条边。那么由于一个点被对称过就会消失，在图上对应为只有一条出边。一共有 n-1 条边且连通，所以这是一棵树。根为最后剩下那个节点编号。

由于对称操作形如 A\gets 2B-A，过程中每个点的坐标一定形如 \sum 2^j (-1)^k x^i。由于 x 足够大，我们可以认为 x 的不同次幂之间的贡献是互不影响的，也就是说只要这个多项式任意一项系数不同，我们就认为它求和的结果不同。

考虑根据这棵树求出最后点所在的位置，设 ans_x 表示点 x 对最后总答案产生的贡献。
在实际过程中，我们一定是以从叶子逐步向上的顺序进行操作，一个点只有在所有叶子都操作完的情况下才能被操作。而考虑一次操作对树上每个点贡献的改变，fa_x 关于 x 对称即令 x 所在的连通块 ans 全部乘 2，fa_x 所在的连通块取反。

那么点 x 在 2^j 这部分的贡献显然是 2^{dep_x}，这只与树的形态有关。另一部分取决于 x 的儿子数量和深度，两个限制是不好求的，我们做这样的转化：只要知道点 x 的正负性（下文称之为“颜色”）是否与其父亲节点相同，即可还原出整棵树的颜色。而一个点每加一次儿子就取反一次，这就只与 fa_{x} 的儿子个数和 x 被连边的顺序有关了。

进一步地，设点 x 的儿子个数为 son_x，则恰有 \lfloor \frac{son_x}{2}\rfloor 个儿子取反偶数次。

性质足够了，考虑 dp。从上到下一层层给这棵树填节点，设 f_{i,j} 表示已经填了 i 个节点（我们不关心是第几层），最后一层有 j 个奇数个儿子的节点。

枚举这一层的节点数 k。那么上一层的 j 个节点均会被下取整掉一个儿子，这层与父亲奇偶性相同的节点总数为 t=\frac{k-j}{2}（奇偶性不对就不合法，跳过这个 k）。接下来我们需要知道当前层儿子数为奇数的节点个数。

枚举 p 表示这一层与父亲颜色相同的节点个数。那么我们至少需要 |t-p| 个奇数儿子的点才能放得下这 p 个节点。而更多的奇数点（|t-p|+2x）是没有意义的，因为我们并不关心下层的点具体每个怎么连，这对实际的贡献没有影响，是树形态不同但最终位置相同的重复解。理解上注意分清“有奇数个儿子”和“取反次数是奇数”。

故有转移：

f_{i+k,|t-p|}\gets f_{i,j}\binom{n-i}{k}\binom{k}{p}

时间复杂度 O(n^4)。

#define int long long
const int N=105,mod=1e9+7;
int n,c[N][N],f[N][N];
il void init(int mx)
{
    for(int i=0;i<=mx;i++)
        for(int j=0;j<=i;j++) c[i][j]=j?(c[i-1][j-1]+c[i-1][j])%mod:1;
}
il void add(int &x,int y) {x=(x+y)%mod;}
signed main()
{
    n=read(); init(n);
    f[1][0]=f[1][1]=n;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            if(!f[i][j]) continue;
            for(int k=j?j:2;k<=n-i;k+=2)
            {
                int t=(k-j)>>1;
                for(int p=0;p<=k;p++) add(f[i+k][abs(p-t)],f[i][j]*c[n-i][k]%mod*c[k][p]);
            }
        }
    printf("%lld\n",f[n][0]);
    return 0;
}