#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 17, B = 317, M = 1e9 + 7;
int n, d[N], x[N], f[N], s[N][B];
void add (int &a, long long b)
{
a += b;
if (a >= M)
{
a -= M;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> d[i] >> x[i];
}
for (int i = n; i; --i)
{
int c = d[i];
f[i] = 1;
if (c)
{
int k = min (x[i], (n - i) / d[i]);
if (k <= B)
{
for (int j = i + c; j <= i + k * c; j += c)
{
add (f[i], f[j]);
}
}
else
{
add (f[i], s[i + c][c] - s[i + (k + 1) * c][c] + M);
}
}
for (int j = 1; j < B; ++j)
{
s[i][j] = (s[i + j][j] + f[i]) % M;
}
}
cout << f[1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |