# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1258030 | efeg | Trains (BOI24_trains) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int n;
vector<int> d,x;
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
cin >> n;
d.resize(n); x.resize(n);
for (int i =0 ;i < n; i++) {
cin >> d[i] >> x[i];
}
int SIZE = sqrt(n);
vector<int> dp(n,0);
vector<vector<int>> cal(SIZE + 100,vector<int>(SIZE + 100,0));
vector<vector<tuple<int,int,int>>> rm(n+10);
dp[0] = 1;
int ans = 0;
for (int i = 0; i < n; i++){
for (auto tp : rm[i]){
int i,di,dpi; tie(i,di,dpi) = tp;
cal[di][i % di] = (cal[di][i % di] - dpi + MOD) % MOD;
}
for (int j = 1; j <= SIZE; j++){
// cout << i << " " << j << " " << i % j << " " << cal[j][i % j] << endl;
dp[i] = (dp[i] + cal[j][i % j]) % MOD;
}
if (d[i] != 0){
if (n <= SIZE * d[i]){
for (int j = 1; j <= x[i]; j++){
int next = i + j * d[i];
if (next >= n) break;
dp[next] = (dp[next] + dp[i]) % MOD;
}
}
else {
cal[d[i]][i % d[i]] = (cal[d[i]][i % d[i]] + dp[i]) % MOD;
int zaman = d[i] * x[i] + i + 1;
if (zaman > n) zaman = n;
rm[zaman].emplace_back(i,d[i],dp[i]);
}
}
ans = (ans + dp[i]) % MOD;
//cout << i << ": " << dp[i] << endl;
}
cout << ans << endl;
return 0;
}