This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long un;
typedef vector<un> vuc;
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
constexpr un M = 1e9 + 7;
#define DIRECT 0
#define CACHE 1
int main(){
un N;
cin >> N;
vuc D(N);
vuc X(N);
REP(i, 0, N){
cin >> D[i] >> X[i];
}
un bound = (un)pow((double)N, 0.6666666);
map<pair<un, un>, un> vyskyty;
REP(i, 0, N){
if (D[i] == 0) continue;
if (vyskyty.find({D[i], i % D[i]}) == vyskyty.end()){
vyskyty[{D[i], i % D[i]}] = min(X[i], (N-i) / D[i]);
}
else{
vyskyty[{D[i], i % D[i]}] += min(X[i], (N-i) / D[i]);
}
}
map<pair<un, un>, un> volba;
FEAC(kv, vyskyty){
pair<un, un> key;
un val;
tie(key, val) = kv;
if (val < bound){
volba[key] = DIRECT;
}
else{
volba[key] = DIRECT;
}
}
vuc DP(N, 0);
DP[0] = 1;
map<un, map<un, un>> cache;
REP(i, 0, N){
FEAC(kv, cache){
un key;
tie(key, ignore) = kv;
if (cache[key].find(i % key) != cache[key].end()){
DP[i] = (DP[i] + cache[key][i % key]) % M;
}
}
if (D[i] == 0) continue;
if (volba[{D[i], i%D[i]}] == DIRECT){
for (un j = i + D[i]; (j < N) and (((j-i) / D[i]) <= X[i]); j += D[i]){
DP[j] = (DP[j] + DP[i]) % M;
}
}
else{
if (cache.find(D[i]) == cache.end()) {
cache[D[i]] = {{i % D[i], DP[i]}};
}
else if (cache[D[i]].find(i % D[i]) == cache[D[i]].end()){
cache[D[i]][i % D[i]] = DP[i];
}
else{
cache[D[i]][i % D[i]] += DP[i];
cache[D[i]][i % D[i]] %= M;
}
}
}
un res = 0;
REP(i, 0, N){
res = (res + DP[i]) % M;
}
cout << res;
}
# | 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... |