题解 CF1146D 【Frog Jumping】
ChthollyTree
2019-04-22 09:14:21
应该可以想到一个O(n) 的做法 求出 $\sum_{i=1}^{n}f(i)$
就是bfs，每次加入一个点i是时候，判断之前 i-a 是否之前可以到达
如果可以，那么点i可以到达，并用点i bfs扩展一波即可
这样每个点最多被遍历1次，所以是O(n)的
------------
然后我们打表找规律,发现当 n > 2*max(a,b)的时候，f(n) = $\frac{n}{gcd(a,b)}+1$
然后在 $i <= 2*max(a,b)$ 时暴力做，否则用规律就行了
比赛的时候其实我找到规律了，但是忘记了小数据可以暴力做这种操作，一直推式子
直到最后10min我才做出来这题。我太菜了
不过总算让 [ChthollyTree](https://codeforces.com/profile/ChthollyTree) 上紫了
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LL long long
#define INF (LL)(0x3f3f3f3f)*(LL)0x3f3f3f3f
#define MAXN 300005
LL n,m;
LL a,b,x;
LL ans = 0;
LL an[MAXN];
bool f[MAXN];
queue<int>q;
LL gcd(LL x,LL y) {
if(x%y != 0) return gcd(y,x%y);
return y;
}
LL orz(LL x) {
return x*(x+1)>>1;
}
LL sqz(LL x,LL mo)
{
if(x % mo == 0) return x/mo;
else return x/mo+1;
}
LL stO(LL n) {
return orz((n+1)/x)*x + ((n+1)%x)*(sqz(n+1,x));
}
int bfs(int i)
{
int ans = 0;
f[0] = 1;
while(!q.empty()) {
int x = q.front();
q.pop();
ans ++;
if(x+a <= i && !f[x+a]) {
f[x+a] = 1;
q.push(x+a);
}
if(x-b >= 0 && !f[x-b]) {
f[x-b] = 1;
q.push(x-b);
}
}
return ans;
}
signed main()
{
cin >> n >> a >> b;
q.push(0);
an[0] = 1;
f[0] = 1;
bfs(0);
for(int i = 1; i <= max(a,b)*2; i ++) {
if(i-a >= 0 &&f[i-a]) {
f[i] = 1;
q.push(i);
an[i] = an[i-1]+bfs(i);
} else {
an[i] = an[i-1];
}
}
x = gcd(a,b);
if(a > b)
swap(a,b);
for(int i = 0; i < min(n+1,2*b); i ++) {
ans += an[i];
}
if(n >= 2*b)
ans += stO(n) - stO(2*b-1);
}
cout<<ans;
return 0;
}
```