AGC022F - Checkers

link

考虑一次操作,相当于选出两个数a,b,合并为2a-b,求最后数字的方案数。

于是初始每个数对最后的数的贡献一定是$(-1)^{c_i}2^{d_i}$,其中$c_i$为$0,1$。

由于$a_k=10^{100k}$,所以一定不会存在两组不同的$c_i,d_i$使得$\sum{a_i(-1)^{c_i}2^{d_i}}$相等。

于是就只要考虑有多少组不同的$c,d$.

考虑把合并方案表示为一个类似于重构树的东西。

每次合并两个数$a,b$,就用一个新点作新根,$a$是它的右子树,$b$是它的左子树。

那么最后每个数的$c_i$就是表示它的叶子到根的路经上是左儿子的点奇偶性,$d_i$就是是右儿子的点的奇偶性。

就会得到一个二叉树。

考虑二叉树转成多叉树。

如果把每个非叶子点和它的左子树根合并成一个点,就会得到一个多叉树。

此时每个子树都是原树的一个子树,子树根就是对应子树左链底,根的每个孩子就是链上每个点的右儿子

此时每个点都对应一个数,到根的路经就是$d_i$。

给每个子树一个「树权」,代表这个子树在原树中子树根的$(-1)^{c_i}$。

每个点还有个点权,就是这个点在原树中的$(-1)^{c_i}$。

假设以$x$为根的子树树权为$1$。如果$x$点权为$1$,那么$x$一定有偶数个孩子,恰好有一半树权是$1$,另一半是$-1$。

否则$x$点权为$-1$,$x$一定有奇数个儿子,$\lceil\frac{s}{2}\rceil$个为$1$,$\lfloor\frac{s}{2}\rfloor$个为$-1$

树权为$-1$全部取反即可。

考虑计算答案。记$f_{n,a,b}$表示有$n$个点,最后一层有$a$个点,且树权有$b$个为$1$的方案数。

枚举有$x$个树权为$1$的点点权取反,有$y$个为$-1$的点点权取反。

如果有一个$1$取反,那么下一层$1$要比$-1$多一个,$-1$也类似。

如果对同一层一个$1$点权取反,同时对一个$-1$点权取反,那么不会对$1$和$-1$的大小关系产生影响,也不会对这一层$1,-1$个数产生影响,没有必要。

于是只用考虑$x=0$或$y=0$的情况。

压缩代码长度之后的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#define int long long
#define F(a,b,c) for(int a=b;a<=c;++a)
const int p=1e9+7;
int f[55][55][55],c[55][55];
signed main(){
int n;
std::cin>>n;
f[1][1][1]=1;
F(i,0,n){
c[i][0]=c[i][i]=1;
F(j,1,i-1)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
F(i,1,n-1)F(j,1,i)F(k,0,j)F(l,0,j)F(w,(k-l>0?k-l:0),(n-i+k-l)>>1)
if(w+l-k+w>0)(f[w+l-k+w+i][w+l-k+w][w]+=f[i][j][k]*c[j][l]%p*c[w+l-k+w+i][i])%=p;
int ans=0;
F(i,1,n)F(j,0,i)ans=(ans+f[n][i][j]*c[i][j])%p;
std::cout<<ans;
return 0;
}

# 计数

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×