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;
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
#define int long long
const int N=1e5+5;
const int mod=1e9+7;
const int sz=320;
int n,d[N],x[N],en[N];
vector <pair <int,int> > v[N];
namespace sub1{
bool ck(){
return n<=10000;
}
int dp[N];
void sol(){
dp[1]=1;
for(int i=2; i<=n; i++){
for(int j=1; j<i; j++){
if(d[j] and (i-j)%d[j]==0 and en[j]>=i) dp[i]=(dp[i]+dp[j]<mod?dp[i]+dp[j]:dp[i]+dp[j]-mod);
}
}
int ans=0;
for(int i=1; i<=n; i++) ans=(ans+dp[i]<mod?ans+dp[i]:ans+dp[i]-mod);
cout<<ans;
}
}
namespace sub2{
bool ck(){
for(int i=1; i<=n; i++) if(d[i]!=1) return 0;
return 1;
}
struct BIT{
#define gb(x) (x)&(-x)
int n;
vector <int> bit;
void init(int _n){
n=_n;
bit.resize(_n,0);
}
void update(int i, int v){
for(; i<n; i+=gb(i)) bit[i]=(bit[i]+v)%mod;
}
void range(int l, int r, int v){
if(l>r) return;
update(l,v);
update(r+1,-v);
}
int get(int i){
int ans=0;
for(; i; i-=gb(i)) ans=(ans+bit[i])%mod;
return ans;
}
}fw;
int dp[N];
void sol(){
fw.init(n+5);
dp[1]=1;
fw.range(2,en[2],1);
int ans=1;
for(int i=2; i<=n; i++){
dp[i]=(fw.get(i)-fw.get(i-1)+mod)%mod;
fw.range(i+1,en[i],dp[i]);
ans=(ans+dp[i])%mod;
}
cout<<ans;
}
}
namespace full{
int dp[N],g[sz+5][sz+5],ans;
void sol(){
dp[1]=1;
for(int i=1; i<=n; i++){
for(int j=1; j<=sz; j++){
dp[i]=(dp[i]+g[j][i%j])%mod;
}
if(d[i]>sz){
for(int j=i+d[i]; j<=en[i]; j+=d[i]) dp[j]=(dp[j]+dp[i])%mod;
}else if(d[i]>0){
g[d[i]][i%d[i]]=(g[d[i]][i%d[i]]+dp[i])%mod;
}
for(auto [j,_d]:v[i]) if(_d<=sz) g[_d][j%_d]=(g[_d][j%_d]-dp[j]+mod)%mod;
}
for(int i=1; i<=n; i++) ans=(ans+dp[i])%mod;
cout<<ans;
}
}
void sol(){
cin>>n;
for(int i=1; i<=n; i++) cin>>d[i]>>x[i],en[i]=min(n,i+d[i]*x[i]);
for(int i=1; i<=n; i++) if(d[i] and d[i]<=sz) v[en[i]].push_back({i,d[i]});
if(sub1::ck()){
sub1::sol();
return;
}
if(sub2::ck()){
sub2::sol();
return;
}
full::sol();
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("arya.inp", "r", stdin);
// freopen("arya.out", "w", stdout);
int tt=1;
//cin>>tt;
while(tt--){
sol();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |