제출 #1267314

#제출 시각아이디문제언어결과실행 시간메모리
1267314g4yuhgTrains (BOI24_trains)C++20
100 / 100
667 ms359480 KiB
//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll> 
#define MP make_pair
#define fi first
#define se second
#define TASK "connect"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define LOG 18
#define endl '\n'
using namespace std;

const ll mod = 1e9 + 7;
const ll S = 320;

void add(ll &u, ll v) {
	u += v;
	if (u >= mod) u -= mod;
}

ll n;
ll d[N], x[N], dp[N];

vector<ll> pf[S + 2][S + 2];

void solve() {
	for (int i = n; i >= 1; i --) {
		dp[i] = 1;
		if (d[i] == 0) {
			dp[i] = 1;
		}
		else {
			if (x[i] <= S || d[i] > S) {
				for (int t = 1; t <= x[i]; t ++) {
					if (i + t * d[i] > n) break;
					add(dp[i], dp[i + t * d[i]]);
				}
			}
			else {
				ll du = i % d[i];
				ll val = 0;
				if (pf[d[i]][du].size() > 0) {
					ll sz = pf[d[i]][du].size(); 
					val = pf[d[i]][du][sz - 1];
					if (sz - x[i] - 1 >= 0) {
						val = val - pf[d[i]][du][sz - x[i] - 1];
						val = (val % mod + mod) % mod;
					}
				}
				add(dp[i], val);
			}
		}
		/*if (i == 1) {
			for (auto it : pf[1][0]) {
				cout << it << " ";
			}
			cout << endl;
		}*/
		for (int j = 1; j <= S; j ++) {
			ll du = i % j;
			if (pf[j][du].size() > 0) {
				pf[j][du].push_back( (pf[j][du].back() + dp[i]) % mod );
			}
			else {
				pf[j][du].push_back(dp[i]);
			}
		}
		//cout << i << " " << dp[i] << endl;
	}
	cout << dp[1];
}

signed main(void) {
	faster;
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> d[i] >> x[i];
	}
	
	solve();
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...