题号是\(\text{51nod}\) 1383和1048
\(n\le 10^6\)
这档分\(O(n\log n)\)或者\(O(n)\)都可以。
\(\log\)的是用\(2\)的幂跑一次完全背包
线性的考虑每个数从为空的序列开始是通过\(+1\)或者集体\(\times 2\)得到的。
\(f[i]=(i\&1)?0:f[i/2]+f[i-1]\)
\(n\le 10^{30}\)
我们先考虑每个二的整数幂有多少种方法凑出来。
\(f[i][j]\)表示最大数是\(2^j\)的数凑出\(2^i\)的方案数。
如果\(f[i][j]=\sum_{k=0}^jf[i-1][k]\times
f[i-1][j]\)
显然在会算重
我们强行让后面方案用的数都大于前面的
也就是去掉小于\(2^k\)产生的贡献，\(f[i-k-1][j-k]\)也就是所有数除了\(2^k\)
\(f[i][j]=\sum_{k=0}^jf[i-1][k]\times
f[i-k-1][j-k]\)
我们要利用\(f\)来计算答案
我们考虑\(2\)进制下，\(g[i][j]\)表示用最大数是\(2^j\)的数凑前\(i\)位的方案数
\(g[i][j]=\sum_{k=0}^jg[i-1][k]\times
f[i-k][j-k]\)
注意某一位是\(1\)的时候才需要更新\(g\)数组，应该记录一下\(g\)的第一维更新了多少次。
其实还没有做完...
因为出题人十(sang)分(xin)友(bing)好(kuang)不给模数，所以你还得写个压位高精。
说实话这东西我找了好久的板子，因为我不会写高精度...
\(\text{oi-wiki}\)上面那个封装好的高精度有点问题，高精度乘法模板都过不了
高精度模板放在代码里面了
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Wint:vector<ll>
{
const static ll BIT=1e8;
Wint(ll n=0) {push-back(n);check();}
Wint& operator=(const char* num)
{
int Len=strlen(num)-1; clear();
for(int i=Len;i>=0;i-=9)
{
push-back(0); ll w=1;
for(int j=i;j>i-9&&j>=0;--j)
back()+=(num[j]^48)*w,w*=10;
}
return *this;
}
Wint& check()
{
while(!empty()&&!back()) pop-back();
if(empty()) return *this;
for(int i=1;i<size();++i)
(*this)[i]+=(*this)[i-1]/BIT,
(*this)[i-1]%=BIT;
while(back()>=BIT)
{
push-back(back()/BIT);
(*this)[size()-2]%=BIT;
}
return *this;
}
};
bool operator<(Wint a,Wint b)
{
if(a.size()!=b.size()) return a.size()<b.size();
for(int i=a.size()-1;i>=0;--i)
if(a[i]!=b[i]) return a[i]<b[i];
return 0;
}
bool operator>(Wint a,Wint b) {return b<a;}
bool operator<=(Wint a,Wint b) {return !(a>b);}
bool operator>=(Wint a,Wint b) {return !(a<b);}
bool operator!=(Wint a,Wint b) {return a<b||b<a;}
bool operator==(Wint a,Wint b) {return !(a<b)&&!(b<a);}
Wint& operator+=(Wint &a,Wint b)
{
if(a.size()<b.size()) a.resize(b.size());
for(int i=0;i<b.size();++i) a[i]+=b[i];
return a.check();
}
Wint operator+(Wint a,Wint b) {return a+=b;}
Wint& operator-=(Wint &a,Wint b)
{
for(int i=0;i<b.size();a[i]-=b[i],++i)
if(a[i]<b[i])
{
int j=i+1;
while(!a[j]) ++j;
while(j>i) --a[j],a[--j]+=Wint::BIT;
}
return a.check();
}
Wint operator-(Wint a,Wint b) {return a-=b;}
Wint operator*(Wint a,Wint b)
{
if(a.empty()&&b.empty()) return a;
Wint n; n.assign(a.size()+b.size()-1,0);
for(int i=0;i<a.size();++i)
for(int j=0;j<b.size();++j)
n[i+j]+=a[i]*b[j];
return n.check();
}
Wint& operator*=(Wint &a,Wint b) {return a=a*b;}
Wint operator/(Wint a,int b)
{
Wint n; bool wp=0; ll t=0;
for(int i=a.size()-1;i>=0;--i)
{
t=t*Wint::BIT+a[i];
if(wp||t/b) wp=1,n.push-back(t/b);
t%=b;
}
reverse(n.begin(),n.end());
return n;
}
Wint& operator/=(Wint &a,int b) {return a=a/b;}
void readX(Wint &n) {char s[1000]; scanf("%s",s); n=s;}
void writeX(Wint n)
{
if(n.empty()) {putchar('0'); return;}
int Len=n.size()-1; printf("%lld",n[Len]);
for(int i=Len-1;i>=0;--i) printf("%08lld",n[i]);
}
typedef --int128 i128;
i128 n;
Wint f[142][142], g[142][142];
i128 read() {
char ch = getchar();
i128 w = 0;
while (ch > '9' || ch < '0') ch = getchar();
while (ch <= '9' && ch >= '0') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
int main() {
ios::sync-with-stdio(false);
n = read();
int limit = 100;
f[0][0] = 1;
for (int i = 1; i <= limit; i++)
for (int j = 0; j <= i; j++) {
if (j == i) f[i][j] = 1;
else for (int k = 0; k <= j; k++) f[i][j] = f[i][j] + f[i - 1][k] * f[i - 1 - k][j - k];
}
g[0][0] = 1;
int cnt = 0;
for (int i = 0; i <= limit; i++) {
if ((n >> (i128)(i)) & 1) {
++cnt;
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= j; k++) g[cnt][j] = g[cnt][j] + g[cnt - 1][k] * f[i - k][j - k];
}
}
}
Wint res;
for (int i = 0; i <= limit; i++) res = res + g[cnt][i];
writeX(res);
return puts(""), 0;
}
|