Submission #1062944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062944		vuavisao	Trains (BOI24_trains)	C++17	100 / 100	115 ms	9868 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;
const int MOD = 1'000'000'000 + 7;

template <int Module>
class Mint {
private:
	int val;

public:
	Mint() : val(0) {};
	Mint(ll _val) {
		val = _val % Module;
		normalization_effect();
	}

public:
	void normalization_effect() {
		/// [- Module, 2 * Module)
		this->val = this->val + (this->val < 0) * Module - (this->val >= Module) * Module;
	}

	int get_val() const { return this->val; }

	Mint operator-() const { return Mint(-this->val); }

	Mint pw(ll exp) const {
		Mint res = 1;
		Mint base = *this;
		while (exp > 0) {
			if(exp & 1ll) res *= base;
			base *= base;
			exp >>= 1ll;
		}
		return res;
	}

	Mint inv() const {
		/// Module is prime
		/// return 〖val〗^(-1)
		return this->pw(Module - 2);
	}

public:
	Mint& operator+=(const Mint& other) {
		this->val += other.val;
		this->normalization_effect();
		return *this;
	}

	Mint& operator-=(const Mint& other) {
		this->val -= other.val;
		this->normalization_effect();
		return *this;
	}

	Mint& operator*=(const Mint& other) {
		this->val = 1ll * this->val * other.val % Module;
		this->normalization_effect();
		return *this;
	}

	Mint& operator/=(const Mint& other) {
		this->operator*=(other.inv());
		return *this;
	}

	Mint& operator++() { this->operator+=(1); return *this; }
	Mint& operator--() { this->operator-=(1); return *this; }

	Mint operator+(const Mint& other) const {
		Mint res = *this;
		res += other;
		return res;
	}

	Mint operator-(const Mint& other) const {
		Mint res = *this;
		res -= other;
		return res;
	}

	Mint operator*(const Mint& other) const {
		Mint res = *this;
		res *= other;
		return res;
	}

	Mint operator/(const Mint& other) const {
		Mint res = *this;
		res /= other;
		return res;
	}

	bool operator==(const Mint& other) const {
		return (this->val == other.val);
	}

public:
	friend ostream& operator<<(ostream& os, const Mint& other) {
		return os << other.val;
	}
};

using mint = Mint<MOD>;

struct event {
	int idx, dist, mod, type;
	event() : idx(0), dist(0), mod(0), type(0) {};
	event(int _idx, int _dist, int _mod, int _type) : idx(_idx), dist(_dist), mod(_mod), type(_type) {};
};

int n;
int dist[N], cnt[N];

vector<event> events[N];

int sqrt_n;
mint pref[320][320];
mint dp[N];

void solve() {
	cin >> n;
	sqrt_n = sqrt(n);
	for (int i = 1; i <= n; ++ i) {
		cin >> dist[i] >> cnt[i];
		if (cnt[i] == 0 || dist[i] == 0) continue;
		if (dist[i] <= sqrt_n) {
			int first = i + dist[i];
			int last = i + min((n - i) / dist[i], cnt[i]) * dist[i];
			if (first <= n) {
				events[first].push_back(event(i, dist[i], i % dist[i], 1));
			}
			if (last + dist[i] <= n) {
				events[last + dist[i]].push_back(event(i, dist[i], i % dist[i], -1));
			}
		}
	}
	dp[1] = 1;
	for (int i = 1; i <= n; ++ i) {
		for (const auto& [idx, d, mod, sign] : events[i]) {
			// cout << idx << ' ' << d << ' ' << mod << ' ' << sign << '\n';
			pref[d][mod] += mint(sign) * dp[idx];
		}
		for (int dist = 1; dist <= sqrt_n; ++ dist) {
			dp[i] += pref[dist][i % dist];
		}
		if (dist[i] > sqrt_n) {
			for (int j = 1; j <= cnt[i]; ++ j) {
				int nxt = i + j * dist[i];
				if (nxt > n) break;
				dp[nxt] += dp[i];
			}
		}
	}
	mint res = 0;
	for (int i = 1; i <= n; ++ i) {
		// cout << dp[i] << " \n"[i == n];
		res += dp[i];
	}
	cout << res;
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	// int t; cin >> t;
	int t = 1;
	while (t-- > 0) {
		solve();
		cout << '\n';
	}
	return (0 ^ 0);
}

/// Code by vuavisao

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29