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;
const int mod=(int)1e9+7;
#define endl '\n'
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
int dp[100002];
void iforgor()
{
int n;
cin>>n;
dp[0]=1;
int pog=sqrt(n);
vector<vector<int>>dp1(pog,vector<int>(pog));
// cout<<pog<<endl;
vector<vector<array<int,3>>>nig(n);
for(int i=0;i<n;i++)
{
int d,x;
cin>>d>>x;
for(int j=1;j<pog;j++){
int lo=i%j;
dp[i]+=dp1[j][lo];
dp[i]%=mod;
}
for(auto j:nig[i])
{
int lo=j[2],dd=j[1],dp1m=j[0];
dp1[dd][lo]=(dp1[dd][lo]-dp1m+mod)%mod;
}
if(x==0||d==0)continue;
if(d>=pog){
for(int j=i+d;j<n;j+=d)
{
x--;
if(x<0)break;
dp[j]+=dp[i];
dp[j]%=mod;
}
}
else
{
int lo=i%d;
dp1[d][lo]+=dp[i];
dp1[d][lo]%=mod;
if((i+d*x)<n)nig[i+d*x].push_back({dp[i],d,lo});
}
}
int ans=0;
for(int i=0;i<n;i++)ans+=dp[i],ans%=mod;
cout<<ans<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
// cin>>t;
while(t--)iforgor();
}
# | 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... |