c/c++语言开发共享CF750G New Year and Binary Tree Paths

题目链接

简单的

设从节点(x)开始不断往左儿子走h-1步，则编号和为(xsum_{i=0}^{h-1}2^i=x(2^h-1))。

若倒数第(i)步走向的是右儿子，则编号和会增加(sum_{j=0}^{i-1}2^j=2^i-1)。

这样，从(x)往下走形成的长为(h)的链中，其中倒数(i,iin t)步时走向右儿子，倒数(i,inotin t)步走向左儿子，这样得到的编号和为

[ x(2^h-1)+sum_{iin t}2^i-|t|=s ]

令(l=lfloorfrac{s}{2^h-1}rfloor)，显然(|t|<hlelog_2(s+1),xle l)。又因为

[ (l-1)(2^h-1)+sum_{iin t}2^i-|t|le s-(2^h-1)+(2^h-h-1)\ =s-h<s ]

故(x>l-1)进而(x=l)，或称对每个(h)有唯一的(x=l)，那么方案数为方程(sum_{iin t}2^i=s+|t|+l(2^h-1))的解的个数。（这显然最多只有一组解）

组合的

从节点(x)的左右儿子出发的两天简单链分别表示为((h_0,t_0),(h_1,t_1))，总的编号和

[ x+2x(2^{h_0}-1)+(2x+1)(2^{h_1}-1)+sum_{iin t_0}2^i+sum_{iin t_1}2^i-|t_0|-|t_1|\ =x(2^{h_0+1}+2^{h_1+1}-3)+2^{h_1}-1+sum_{iin t_0}2^i+sum_{iin t_1}2^i-|t_0|-|t_1|=s ]

大胆猜想(h_0,h_1)确定时有唯一的(x=lfloorfrac{s-2^{h_1}+1}{2^{h_0+1}+2^{h_1+1}-3}rfloor)。

接着问题转变为在({2^1,2^2,cdots,2^{h_0-1}},{2^1,2^2,cdots,2^{h_1-1}})中一共选取(n)个数之和等于(s-(cdots)+n)（qaq）的方案数。

考虑枚举(n)，设(f[i,j,0/1])表示考虑完前(i)个指数后，已经选了(j)个数字，这一位（二进制末尾第(i+1)位）为是否进位的方案数。其中(f[0,0,0]=1)。

答案是(sum_{h_0,h_1}(sum_n f[max(h_0,h_1),n,0]))。时间复杂度(o(log_2^5s))。

#include <bits/stdc++.h> #define ll long long  using namespace std; const int n=53;  ll s,l,ans; ll p[n]={1}; ll f[n][n*2][2];  int main() {     scanf("%lld",&s); l=log2(s+1);     for(int i=1; i<n; ++i) p[i]=p[i-1]<<1;     for(int h=1; h<=l; ++h) {         ll x=s%(p[h]-1);         for(int i=h; i; --i) if(x>=p[i]-1) x-=p[i]-1;         ans+=(!x);     }     for(int h0=1; h0<l; ++h0)     for(int h1=1; s+1-p[h1]>=p[h0+1]+p[h1+1]-3; ++h1) {         ll x=(s+1-p[h1])/(p[h0+1]+p[h1+1]-3);         ll r=(s+1-p[h1])%(p[h0+1]+p[h1+1]-3);         if(!r) {ans++; continue;}         if(h0==1&&h1==1) {ans+=(s==x*5+1); continue;}         for(int n=1; n<=h0+h1; ++n) {             ll c=r+n,l=log2(c);             if(c&1) continue;             memset(f[0],0,sizeof f[0]); f[0][0][0]=1;             for(int i=1; i<=l; ++i) {                 int d=(c>>i)&1; memset(f[i],0,sizeof f[i]);                 for(int j=0; j<=i+i-2&&j<=n; ++j)                 for(int k=0; k<2; ++k) if(f[i-1][j][k])                      for(int x=0; x<2; ++x) if(!x||i<h0)                     for(int y=0; y<2; ++y) if(!y||i<h1)                          if(((k+x+y)&1)==d) f[i][j+x+y][(k+x+y)>>1]+=f[i-1][j][k];             }             ans+=f[l][n][0];         }     }     printf("%lldn",ans);     return 0; }

不知道1k+ms是怎么跑出来的