이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10,
M = 1'000'000'007,
S = 400;
int n;
int d[N], x[N];
void add(int& x, const int& y) {
x += y;
if (x >= M) x -= M;
};
vector<tuple<int, int, int>> save[N];
int c[S + 10][S + 10];
int f[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> d[i] >> x[i];
f[1] = 1;
for (int i = 1; i <= n; ++i) {
int& ret = f[i];
for (const auto& [size, mod, value] : save[i]) add(c[size][mod], M - value);
for (int j = 1; j <= S; ++j) add(ret, c[j][i % j]);
if (!d[i]) continue;
if (d[i] > S) {
for (int j = 1; j <= x[i]; ++j) {
int t = i + j * d[i];
if (t > n) break;
add(f[t], ret);
}
continue;
}
add(c[d[i]][i % d[i]], ret);
save[min(1ll * n, 1ll * i + d[i] * x[i]) + 1].emplace_back(d[i], i % d[i], ret);
}
int answer = 0;
for (int i = 1; i <= n; ++i) add(answer, f[i]);
cout << answer << "\n";
}
# | 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... |