## 【BZOJ 4725】[POI2017] Reprezentacje ró?nicowe

### 解题报告

$63$项之后的，我们可以推公式推出来答案是多少

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void insert(int w) {
for (int i=w-1;i;i--) {
if (abs(f[w]-f[i]) >= N) break;
vis[abs(f[w]-f[i])] = 1;
}
}

inline int query() {
for (int i=1;i;i++)
if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
for (int j=2;j;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] == w) {
L[id] = i; R[id] = j;
return;
}
}
}
}

inline void query(int w) {
for (int j=2;j;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] == w) {
cout<<j<<' '<<i<<endl;
return;
}
}
}
}

int main() {
f[1] = 1; f[2] = 2; vis[1] = 1;
for (int i=3;i<=120;i++) {
if (i&1) f[i] = f[i-1] << 1;
else f[i] = f[i-1] + query();
insert(i);
}
for (int j=2;j<=63;j++) {
for (int i=1;i<j;i++) {
if (f[j] - f[i] > 1e9) continue;
que[++tot] = f[j] - f[i];
}
}
que[++tot] = (1e9) + 10;
sort(que+1, que+1+tot);
for (int i=1;i<tot;i++) Get_Ans(que[i], i);