题目
给你1,2,4,8,….所有2次幂的数字各两个，你有多少种取的方法保证取得数字和为n(1<=n<=10^18)
不同的方法表示至少有一种数字取的个数不同
题解：
对于题目给定3进制定义
$a_ka_{k-1}a_{k-2}…a_1a_0$表示每一个i号位置上的代表了$2^i$取$a_i$个，那么只要求出有多少种组合保证
$n = a_0∗2^0+a_1∗2^1+…+a_k∗2^k$即可，且$0 \le a_i \le 2$
重要性质
$a_{i+1}a_ia_{i-1} \Leftrightarrow (a_{i+1}-1)(a_i+2)(a_{i-1}) \Leftrightarrow (a_{i+1}-1)(a_i+1)(a_{i-1}+2)$
也就是100 -> 020 -> 012
下降的定义： 我们称从当前位置上的数字-1，转化成下一个位置+2，叫一次当前位置的下降，所以100->020是$a_2$的一次下降，020->012是$a_1$的一次下降。
但要注意的是加的过程中当前位置的数字始终不能超过2.
那么我们很容易就发现有一点很关键:
如果有连续的1比如 1100 我们总是从最低位开始下降，然后再轮到高位，不然会发生重复，那么低位1下降后，其实高位的1只有一种选择只能在当前位置下降一次，且必然是朝着向下一位+2上转移，因为下下个位置已经被前面的1下降的时候至少占据了1，下下个位置+2>=3.
那么多个连续的1，只有当i号的1下降了，i+1号才能选择下降且只能下降一个位置，只有第一个1能下降p个位置，p表示连续0的个数
考虑2的存在，假设数字由t个整数然后接着p个0组成，那么在$a_{p+k}$位置上第一次出现了2，很容易发现p+k后面的正数无法下降，因为一次下降只-1，那么p+k的位置少永远都会留下一个正数，后面的数字不能再下降。
各类函数的定义
根据上面说的：
- f(p)定义：表示一个数字n是由1或者2后面跟了p个0的形式构成，那么可构成这个n的方法总数就称为f(p)，那么就表示只有开头的1或者2可以下降，且最多下降p次，包括自己本身，我们就可以得到
$$
f(p) = p+1
$$$f_k(p)$定义：表示一个数字n由一段连续的正数然后跟着p个连续的0，k表示从0之后出现的正数到第一次出现2的位置所有正数的个数，如果全是1，那么就是k表示所有正数个数。根据上文所说，只有前k个正数可下降，且只能下降一个位置，只有第一个数字可下降p个位置，所以
$$
f_k(p) = k(f(p)-1)+1 = kp+1
$$
分段：将整串数字分割成每段都是连续的正数和连续的0组成，比如1210002001100可以分成3段：(1)121000 (2)200 (3)1100。
$g(i)$：根据分段后的数字，第i段的k和p都可以轻松统计出来，那么g(i)就表示第i段可形成的数字组合数。
$$
g(i) = f_k(p)
$$
分段后每段都是单独存在的，因为后面的段的数字无法下降到其他段（只有一种情况除外，那就是第i段没有2出现，那么第i段的最高位置可以下降为0，这个0de的位置可以被i+1段的数字下降占据），其他情况是独立存在的，符合方法数的乘法原则。每一段的计算都根据$f_k(p)$即可。然后区别讨论。$sum1(i)$：表示前i段所得到的方法总数，且最高位保证不是0
每次要注意区别下一段是否占据了上一段首位元素。
(1) 第i+1段正数都是1的情况下：
$sum1(i+1) = (g(i+1)-p[i+1])∗(sum1(i)+sum2[i])+(k_{i+1}-1)∗sum2(i) \quad k_{i+1}表示第i+1段k的值$
(2) 第i+1段正数出现2的情况下：
$sum1(i+1) = g(i+1)∗(sum1(i)+sum2(i))+k_{i+1}∗sum2(i)$
$sum2(i)$：表示前i段所得到的方法总数，且最高位保证是0
(1) 第i+1段正数都是1的情况下：
$$
sum2(i+1) = p_{i+1}∗(sum1(i)+sum2(i))+sum2(i)
$$
(2) 第i+1段正数出现2的情况下：
$$
sum2(i+1) = 0
$$123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081using namespace std;LL bits[63];void init(){for(int i=0 ; i<63 ; i++) bits[i] = 1LL<<i;}int* ll_to_3bit(LL n){int *number = new int[63];for(int i=62 ; i>=0 ; i--){number[i] = n/bits[i];n = n%bits[i];}return number;}void show(int *a , int n){for(int i=0 ; i<n ; i++) cout<<a[i]<<" ";cout<<endl;}LL sum1[63] , sum2[63] , g[63] , p[63] , k[63] , is2[63] , tot; //tot表示有多少段,is2[i]表示第i段是否有2void decompose(int * a , int n){tot = 0;int cnt0 = 0 , st12 = -1 , st2 = -1; //cnt0统计当前段0的个数，st12表示当前段第一个正数的位置，获取到当前段第一个2的位置for(int i=0 ; i<n ; i++){if(a[i] == 0){if(st12 >= 0){//获取到了一段p[tot] = cnt0;if(st2<0) k[tot] = i-st12, is2[tot]=0;else k[tot] = st2-st12+1, is2[tot]=1;g[tot] = k[tot]*p[tot]+1;tot++ , cnt0 = 0 , st12 = st2 = -1;}cnt0++;}else if(a[i] == 1){if(st12<0) st12 = i;}else{if(st12<0) st12 = i;if(st2<0) st2 = i;}}//外部不用在处理，因为2^62>10^18，一定会在里面处理所有段}LL solve(){if(is2[0])sum1[0] = k[0]*p[0]+1 , sum2[0] = 0;elsesum1[0] = (k[0]-1)*p[0]+1 , sum2[0] = p[0];for(int i=0 ; i<tot-1 ; i++){if(!is2[i+1]) sum1[i+1] = (g[i+1]-p[i+1])*(sum1[i]+sum2[i])+(k[i+1]-1)*sum2[i];else sum1[i+1] = g[i+1]*(sum1[i]+sum2[i])+k[i+1]*sum2[i];if(!is2[i+1]) sum2[i+1] = p[i+1]*(sum1[i]+sum2[i])+sum2[i];else sum2[i+1] = 0;cout<<i+1<<" "<<sum1[i+1]<<" "<<sum2[i+1]<<endl;}return sum1[tot-1]+sum2[tot-1];}int main(){init();LL n = 6;int * number = ll_to_3bit(n);//举个例子 1011100010011number[0] = number[1] = number[4] = number[8] = number[9] = number[10] = number[12] = 1;number[2] = number[3] = number[7] = number[5] = number[6] = number[11] = 0;decompose(number, 63);cout<<solve()<<endl;return 0;}
