#include<bits/stdc++.h>
#include<random>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
using namespace std;
const ll N = 100009;
const ll sz = 40;
vector<ll> seg[sz+1][sz+1];
vector<ll> lazy[sz+1][sz+1];
ll ans[N] , d[N] , x[N];
ll n;
const ll m = 1e9+7;
void se(ll j , ll md , ll x , ll l , ll r , ll l1 , ll r1 , ll val)
{
if(l>r1||r<l1)
return;
if(l>=l1&&r<=r1)
{
lazy[j][md][x]=(lazy[j][md][x]+val)%m;
return;
}
se(j,md,lc,l,mid,l1,r1,val);
se(j,md,rc,mid+1,r,l1,r1,val);
}
ll sg(ll j , ll md , ll x , ll l , ll r , ll idx)
{
if(l>idx||r<idx)
return 0;
if(l==r)
{
seg[j][md][x]+=lazy[j][md][x];
lazy[j][md][x]=0;
seg[j][md][x]%=m;
return seg[j][md][x];
}
lazy[j][md][lc]=(lazy[j][md][lc]+lazy[j][md][x])%m;
lazy[j][md][rc]=(lazy[j][md][rc]+lazy[j][md][x])%m;
lazy[j][md][x]=0;
return sg(j,md,lc,l,mid,idx) + sg(j,md,rc,mid+1,r,idx);
}
int main()
{
cin >> n;
for(int i = 0 ; n>i ; i++)
cin >> d[i] >> x[i];
for(int j = 1 ; sz>=j ; j++)
{
for(int md = 0 ; j>md ; md++)
{
seg[j][md].resize(4*max(1LL,(n-md-1)/j+1));
lazy[j][md].resize(4*max(1LL,(n-md-1)/j+1));
}
}
ans[0]=1;
ll an = 0;
for(int i = 0 ; n>i ; i++)
{
for(int j = 1 ; sz>=j ; j++)
{
ll md = i%j;
ans[i]+=sg(j,md,1,0,(n-md-1)/j,i/j);
}
ans[i]%=m;
an+=ans[i];
an%=m;
if(d[i]==0)
continue;
ll s = min((n-i+1)/d[i],x[i]);
if(s<=100000/sz)
{
for(int j = i+d[i] ; n>j&&x[i]-- ; j+=d[i])
{
ans[j]+=ans[i];
ans[j]%=m;
}
continue;
}
ll j = d[i];
ll md = i%j;
se(j,md,1,0,(n-md-1)/j,i/j,min(i/j+x[i],(n-md-1)/j),ans[i]);
}
cout << an;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
13 |
Correct |
0 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
13 |
Correct |
0 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
604 KB |
Output is correct |
20 |
Correct |
60 ms |
21596 KB |
Output is correct |
21 |
Correct |
15 ms |
8028 KB |
Output is correct |
22 |
Correct |
70 ms |
25760 KB |
Output is correct |
23 |
Correct |
50 ms |
16728 KB |
Output is correct |
24 |
Correct |
27 ms |
10840 KB |
Output is correct |
25 |
Correct |
60 ms |
23244 KB |
Output is correct |
26 |
Correct |
32 ms |
11864 KB |
Output is correct |
27 |
Correct |
62 ms |
22108 KB |
Output is correct |
28 |
Correct |
78 ms |
25944 KB |
Output is correct |
29 |
Correct |
72 ms |
25932 KB |
Output is correct |
30 |
Correct |
71 ms |
25948 KB |
Output is correct |
31 |
Correct |
70 ms |
25952 KB |
Output is correct |
32 |
Correct |
70 ms |
25936 KB |
Output is correct |
33 |
Correct |
66 ms |
25904 KB |
Output is correct |
34 |
Correct |
64 ms |
25888 KB |
Output is correct |
35 |
Correct |
73 ms |
25704 KB |
Output is correct |
36 |
Correct |
70 ms |
25928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
51 ms |
16960 KB |
Output is correct |
3 |
Correct |
31 ms |
11864 KB |
Output is correct |
4 |
Correct |
64 ms |
22104 KB |
Output is correct |
5 |
Correct |
694 ms |
196800 KB |
Output is correct |
6 |
Correct |
957 ms |
255500 KB |
Output is correct |
7 |
Correct |
961 ms |
255412 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
72 ms |
25812 KB |
Output is correct |
12 |
Correct |
962 ms |
255940 KB |
Output is correct |
13 |
Correct |
0 ms |
600 KB |
Output is correct |
14 |
Correct |
75 ms |
25960 KB |
Output is correct |
15 |
Correct |
986 ms |
255684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
502 ms |
122968 KB |
Output is correct |
2 |
Correct |
365 ms |
102224 KB |
Output is correct |
3 |
Correct |
971 ms |
255944 KB |
Output is correct |
4 |
Correct |
672 ms |
182868 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
88 ms |
25924 KB |
Output is correct |
8 |
Correct |
982 ms |
255924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
0 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
0 ms |
604 KB |
Output is correct |
13 |
Correct |
0 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
604 KB |
Output is correct |
18 |
Correct |
0 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
604 KB |
Output is correct |
20 |
Correct |
60 ms |
21596 KB |
Output is correct |
21 |
Correct |
15 ms |
8028 KB |
Output is correct |
22 |
Correct |
70 ms |
25760 KB |
Output is correct |
23 |
Correct |
50 ms |
16728 KB |
Output is correct |
24 |
Correct |
27 ms |
10840 KB |
Output is correct |
25 |
Correct |
60 ms |
23244 KB |
Output is correct |
26 |
Correct |
32 ms |
11864 KB |
Output is correct |
27 |
Correct |
62 ms |
22108 KB |
Output is correct |
28 |
Correct |
78 ms |
25944 KB |
Output is correct |
29 |
Correct |
72 ms |
25932 KB |
Output is correct |
30 |
Correct |
71 ms |
25948 KB |
Output is correct |
31 |
Correct |
70 ms |
25952 KB |
Output is correct |
32 |
Correct |
70 ms |
25936 KB |
Output is correct |
33 |
Correct |
66 ms |
25904 KB |
Output is correct |
34 |
Correct |
64 ms |
25888 KB |
Output is correct |
35 |
Correct |
73 ms |
25704 KB |
Output is correct |
36 |
Correct |
70 ms |
25928 KB |
Output is correct |
37 |
Correct |
0 ms |
600 KB |
Output is correct |
38 |
Correct |
51 ms |
16960 KB |
Output is correct |
39 |
Correct |
31 ms |
11864 KB |
Output is correct |
40 |
Correct |
64 ms |
22104 KB |
Output is correct |
41 |
Correct |
694 ms |
196800 KB |
Output is correct |
42 |
Correct |
957 ms |
255500 KB |
Output is correct |
43 |
Correct |
961 ms |
255412 KB |
Output is correct |
44 |
Correct |
1 ms |
600 KB |
Output is correct |
45 |
Correct |
0 ms |
604 KB |
Output is correct |
46 |
Correct |
0 ms |
604 KB |
Output is correct |
47 |
Correct |
72 ms |
25812 KB |
Output is correct |
48 |
Correct |
962 ms |
255940 KB |
Output is correct |
49 |
Correct |
0 ms |
600 KB |
Output is correct |
50 |
Correct |
75 ms |
25960 KB |
Output is correct |
51 |
Correct |
986 ms |
255684 KB |
Output is correct |
52 |
Correct |
502 ms |
122968 KB |
Output is correct |
53 |
Correct |
365 ms |
102224 KB |
Output is correct |
54 |
Correct |
971 ms |
255944 KB |
Output is correct |
55 |
Correct |
672 ms |
182868 KB |
Output is correct |
56 |
Correct |
1 ms |
604 KB |
Output is correct |
57 |
Correct |
0 ms |
604 KB |
Output is correct |
58 |
Correct |
88 ms |
25924 KB |
Output is correct |
59 |
Correct |
982 ms |
255924 KB |
Output is correct |
60 |
Correct |
983 ms |
213076 KB |
Output is correct |
61 |
Correct |
1035 ms |
255572 KB |
Output is correct |
62 |
Correct |
1157 ms |
255084 KB |
Output is correct |
63 |
Correct |
974 ms |
255484 KB |
Output is correct |
64 |
Correct |
1012 ms |
256596 KB |
Output is correct |
65 |
Correct |
1059 ms |
255944 KB |
Output is correct |
66 |
Correct |
1033 ms |
255824 KB |
Output is correct |
67 |
Correct |
1027 ms |
256080 KB |
Output is correct |
68 |
Correct |
956 ms |
255824 KB |
Output is correct |
69 |
Correct |
1002 ms |
255316 KB |
Output is correct |
70 |
Correct |
938 ms |
255824 KB |
Output is correct |
71 |
Correct |
950 ms |
255648 KB |
Output is correct |
72 |
Correct |
1055 ms |
255648 KB |
Output is correct |