什么是网站内页,泉州晋江网站建设,建设企业网站怎么样,wordpress购物模板CF750G New Year and Binary Tree Pathsdescriptionsolutioncodedescription
题目链接
一颗无穷个节点的完全二叉树。
求有多少条树上的简单路径编号和为 s。 s≤1e15s\le 1e15s≤1e15
solution 一条单链的情况 考虑从节点xxx开始走一条节点个数是hhh的链#xff08;链长为…
CF750G New Year and Binary Tree Pathsdescriptionsolutioncodedescription
题目链接
一颗无穷个节点的完全二叉树。
求有多少条树上的简单路径编号和为 s。
s≤1e15s\le 1e15s≤1e15
solution 一条单链的情况 考虑从节点xxx开始走一条节点个数是hhh的链链长为h−1h-1h−1 假设从上往下一直往左子树走【x,2x,4x,8x...x,2x,4x,8x...x,2x,4x,8x...】 则贡献为x∑i0h−12i(2h−1)xx\sum_{i0}^{h-1}2^i(2^h-1)xx∑i0h−12i(2h−1)x 若链从下往上的第i∈[1,h)i\in[1,h)i∈[1,h)个点是右儿子则会给标号和带来独立的∑j0i−12j2i−1\sum_{j0}^{i-1}2^j2^i-1∑j0i−12j2i−1贡献 可以解出xxx的取值只能是⌊s2h−1⌋\lfloor\frac{s}{2^h-1}\rfloor⌊2h−1s⌋ 证明假设取x−1x-1x−1且这条长hhh的链全走右子树的贡献是 (2h−1)(x−1)∑i1h−1(2i−1)2hx−x−2h12h−1−h(2h−1)x−h(2h−1)x(2^h-1)(x-1)\sum_{i1}^{h-1}(2^i-1)2^hx-x-2^h12^h-1-h(2^h-1)x-h (2^h-1)x(2h−1)(x−1)∑i1h−1(2i−1)2hx−x−2h12h−1−h(2h−1)x−h(2h−1)x 这已经是最大的不是选xxx产生的可能贡献了所以只能是xxx 这里同样经典的可以判断能否用【1,3,...,2h−1−11,3,...,2^{h-1}-11,3,...,2h−1−1】构造出s−(2h−1)xs-(2^h-1)xs−(2h−1)x先用大的开始尝试从最大的往小的开始一个一个试有点类似倍增的思想不断逼近直到相等的感觉 分叉情况两条子链在根节点拼接 假设根节点为xxx设xxx左儿子开始向下的链长度为h1h_1h1右儿子开始向下的链长度为h2h_2h2枚举h1,h2∈[1,log2s]h_1,h_2\in[1,\text{log}_2^s]h1,h2∈[1,log2s] 假设这两条链都往各自的左儿子走贡献是 x2x(2h1−1)(2x1)(2h2−1)(2h112h21−3)x2h2−1x2x(2^{h_1}-1)(2x1)(2^{h_2}-1)(2^{h_11}2^{h_21}-3)x2^{h_2}-1x2x(2h1−1)(2x1)(2h2−1)(2h112h21−3)x2h2−1 同理xxx的位置也是唯一确定的即⌊s−(2h2−1)2h112h21−3⌋\lfloor\frac{s-(2^{h_2}-1)}{2^{h_11}2^{h_21}-3}\rfloor⌊2h112h21−3s−(2h2−1)⌋ 令tststs减去上面的贡献 同时考虑怎么用各自某一层走右儿子产生的贡献【1,3,...,2h1−1;1,3,...,2h2−11,3,...,2^{h_1}-1;1,3,...,2^{h_2}-11,3,...,2h1−1;1,3,...,2h2−1】来构造出ttt转换一下考虑用【2,22,...,2h1;2,22,...,2h22,2^2,...,2^{h_1};2,2^2,...,2^{h_2}2,22,...,2h1;2,22,...,2h2】来凑ttt 枚举选了nnn个数判断能不能用这些数凑出tntntn 这里的实现考虑使用数位dpdpdpO(h1h2)O(h_1h_2)O(h1h2)求出结果 设fi,j,k:f_{i,j,k}:fi,j,k: 前iii位h1h_1h1和h2h_2h2两条链的状态一共选了jjj个222的次方【可能选了222^2222i−1...2^{i-1}...2i−1...反正一共选了jjj个】是否有进位k1/0k1/0k1/0的方案数 对于每一位枚举h1h_1h1链和h2h_2h2链上的选择情况s1,s2s_1,s_2s1,s2 注意到如果ih1ih_1ih1这一位是不能选111【表示进位】的h2h_2h2同理 则可以得到转移方程f[i1][js1s2][s1s2k2]∑f[i][j][k](s1s2k≡⌊tn2i(mod2)⌋)f[i1][js_1s_2][\frac{s_1s_2k}{2}]\sum f[i][j][k]\quad\Big(s_1s_2k\equiv \lfloor\frac{tn}{2^i}\pmod 2\rfloor\Big)f[i1][js1s2][2s1s2k]∑f[i][j][k](s1s2k≡⌊2itn(mod2)⌋)
时间复杂度为O(log5s)O(\text{log}^5s)O(log5s)
code
#include cmath
#include cstdio
#include cstring
#define maxn 60
#define int long long
int s, m, now;
int f[2][maxn 1][2], mi[maxn];int calc( int goal, int q, int h1, int h2, int cnt ) {memset( f[now], 0, sizeof( f[now] ) );f[now][0][0] 1;for( int i 1;i log2( goal ) 1;i ) {int d goal i 1;now ^ 1;memset( f[now], 0, sizeof( f[now] ) );for( int j 0;j ( i - 1 1 );j ) //到i-1及以前可以一共选了[0,(i-1)*2]个数 左儿子(h1)链的选择和右儿子(h2)链的选择 for( int k 0;k 1;k )if( f[now ^ 1][j][k] )for( int s1 0;s1 1;s1 )if( ! s1 or i h1 )for( int s2 0;s2 1;s2 )if( ! s2 or i h2 )if( ( k s1 s2 ) % 2 d ) //判断同余 f[now][j s1 s2][( k s1 s2 ) / 2] f[now ^ 1][j][k];}return f[now][cnt][0];
}signed main() {int ans 0;scanf( %lld, s );mi[0] 1;for( int i 1;i 60;i ) {mi[i] mi[i - 1] 1;if( mi[i] s and mi[i - 1] s ) m i;}for( int i 1;i m;i ) { //单链的构造 int x s / ( mi[i] - 1 );if( x 0 ) continue;int t s - x * ( mi[i] - 1 );for( int j i - 1;~ j;j -- )if( t mi[j] - 1 ) t - mi[j] - 1;if( ! t ) ans ;}for( int h1 1;h1 m;h1 )for( int h2 1;mi[h2] - 1 s;h2 ) {int x ( s - mi[h2] 1 ) / ( mi[h1 1] mi[h2 1] - 3 );if( x 0 ) continue;int t ( s - mi[h2] 1 ) - x * ( mi[h1 1] mi[h2 1] - 3 );if( ! t ) { ans ; continue; }if( h1 1 and h2 1 ) { ans ( t 5 * x 1 ); continue; } //x 2x 2x1 - 5x1for( int n 1;n h1 h2;n ) //枚举选了n个右儿子 if( ( ( t n ) 1 ) 0 ) ans calc( t n, x, h1, h2, n );}printf( %lld\n, ans );return 0;
}
