Atcoder AGC022F :Checkers

传送门

题解：

如果我们让A关于B对称，那么就把B连向A。容易发现任何一个方案最终都会形成一棵树。

考虑每个点对最终答案的贡献，容易发现为$2^d$。不过还有一个$pm1$的系数。
两个方案不同当且仅当某个系数不同，具体就是某个数的深度或者正负号不同。

关于$pm 1$系数我们发现，当一个点的儿子个数为$k$，有$lfloor frac{k}{2} rfloor$个儿子会被取反，而且当$k$为奇数时，自己的状态也会被取反。
所以一个点的正负只和父亲的正负，父亲的奇偶，自己的奇偶有关。
关于层数，我们可以按层枚举来保证方案不同。

具体的DP：
发现要和父亲的正负有关不是很优美，我们可以先差分一下这棵树的正负号的系数，原来如果自己和父亲的正负号不同，则新树中自己的正负号为$-1$，否则为$1$。
这样差分后一层的状态就只和上一层的奇数儿子的点的个数有关了（只用管和父亲一不一样，不用管具体符号）。

记$f_{i,j}$表示个数为$i$，最后一层的奇数点有$j$个的方案数。然后枚举有$x$个数与父节点相同，$y$个不同。如果不考虑这一层自己是奇数点的影响的话，正的点应该是$j+frac{x+y-j}{2}$个，相当于每个奇数点先自带一个，然后再成对出现。
那么我们就要取反$|j+frac{x+y-j}{2}-x|$个点来达到我们要枚举的状态。
取反就相当于下一层会有这么多个奇数点，直接转移过去就好了。同时再多取反两个符号不同的是非法的，因为这种方案DP出来的方案都会被不取反他们的情况统计到。所以转移是$O(1)$的。

时间复杂度$O(n^4)$,稍微优化一下可以达到$O(n^3)$。

关于$O(n^3)$的优化：
发现如果$i+x,j-x$都一样，那么转移到的地方也一样。我们先$f_{i,j} rightarrow g_{i+x,j-x}$，再$g_{i,j} rightarrow f_{x,y}即可$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=55, mod=1e9+7;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int mul(int x,int y) {return (LL)x*y%mod;}

inline void add1(int &x,int y) {x=add(x,y);}

int n,f[N][N],c[N][N],g[N][N];

int main() {
    cin>>n;
    f[1][0]=f[1][1]=1;
    for(int i=0;i<=n;i++) c[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=add(c[i-1][j-1],c[i-1][j]);
    for(int i=1;i<n;i++)
        for(int j=0;j<=i;j++) if(f[i][j]) 
            for(int x=0;x+i<=n;++x)
                for(int y=0;x+y+i<=n;++y) if((x+y) && (x+y>=j) && (!((x+y-j)&1)))
                    add1(f[i+x+y][abs((x+y-j)/2+j-x)],mul(f[i][j],mul(c[i+x+y][x+y],c[x+y][x])));
    cout<<f[n][0]<<'n';
}

最后

以上就是犹豫发箍为你收集整理的Atcoder AGC022F :Checkers的全部内容，希望文章能够帮你解决Atcoder AGC022F :Checkers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。