제출 #994559

#제출 시각아이디문제언어결과실행 시간메모리
994559emptypringlescanTrains (BOI24_trains)C++17
34 / 100
146 ms6760 KiB
#include <bits/stdc++.h>
using namespace std;
const long long buc=316,mod=1000000007;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	pair<long long,long long> arr[n+1];
	for(int i=1; i<=n; i++) cin >> arr[i].first >> arr[i].second;
	long long dp[n+1];
	memset(dp,0,sizeof(dp));
	dp[1]=1;
	long long smol[buc+5][buc+5]; //div, rem
	memset(smol,0,sizeof(smol));
	vector<pair<int,long long> > stop[n+1];
	long long ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<buc; j++){
			dp[i]+=smol[j][i%j];
			dp[i]%=mod;
		}
		ans+=dp[i];
		ans%=mod;
		for(auto j:stop[i]){
			smol[j.first][i%j.first]-=j.second;
			smol[j.first][i%j.first]%=mod;
			if(smol[j.first][i%j.first]<0) smol[j.first][i%j.first]+=mod;
		}
		if(arr[i].first==0) continue;
		else if(arr[i].first<buc){
			smol[arr[i].first][i%arr[i].first]+=dp[i];
			smol[arr[i].first][i%arr[i].first]%=mod;
			if(i+arr[i].first*arr[i].second<=n){
				stop[i+arr[i].first*arr[i].second].push_back({arr[i].first,dp[i]});
			}
		}
		else{
			for(int j=1; j<=arr[i].second; j++){
				if(i+j*arr[i].first>n) break;
				dp[i+j*arr[i].first]+=dp[i];
				dp[i+j*arr[i].first]%=mod;
			}
		}
	}
	cout << ans;
}
#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...