题目大意
有
n
n
n 个人排队准备录视频，轮到第
i
i
i 个人的时候，如果他被商家钦定，或者排他前面的至少有
a
i
a_i
ai 个人录视频，他就会录视频。问商家至少钦定多少人，使得最终录视频的人数
≥
m
\ge m
≥m。
m
≤
n
≤
5
×
1
0
7
m \le n \le 5 \times 10^7
m≤n≤5×107，由于输入过大，仅输入
a
1
a_1
a1，接下来给出
k
k
k 段生成器，每段生成
c
i
c_i
ci 个
a
a
a（保证
∑
i
=
1
k
c
i
=
n
−
1
\sum_{i=1}^k c_i=n-1
∑i=1kci=n−1），每个生成器形如
a
i
=
(
x
a
i
−
1
+
y
)
m
o
d
z
a_i=(x a_{i-1}+y) \bmod z
ai=(xai−1+y)modz，
z
z
z 为质数。
k
≤
1
0
5
k \le 10^5
k≤105
4s, 64MB
\\
\\
\\
题解
思考许久，转头发现，这个空间，甚至连
n
n
n 的数组都存不下。。。
感觉题解给得很妙啊。
考虑最后一个人，如果
a
n
<
m
a_n<m
an<m，他是一定会录视频的，因此转化为子任务
(
n
−
1
,
m
−
1
)
(n-1,m-1)
(n−1,m−1)；
否则，如果
a
n
≥
m
a_n \ge m
an≥m 且
n
=
m
n=m
n=m，这个人必须被钦定，不然不合法，因此也转化为子任务
(
n
−
1
,
m
−
1
)
(n-1,m-1)
(n−1,m−1)；
否则，
a
n
≥
m
a_n \ge m
an≥m 且
n
>
m
n>m
n>m，此时要么前
n
−
1
n-1
n−1 个人已经选出了
m
m
m 个，那么第
n
n
n 人直接扔了就好；要么前
n
−
1
n-1
n−1 个人只选了
m
−
1
m-1
m−1 个，想要钦定第
n
n
n 个人，但是钦定前面的人只会使答案更优，所以不会有该情况。也就是说，
a
n
≥
m
a_n \ge m
an≥m 且
n
>
m
n>m
n>m 时，直接忽略最后一个人，转化为子任务
(
n
−
1
,
m
)
(n-1,m)
(n−1,m)。
于是这样到这做一遍就做好了。
由于空间不允许存下整个数组，可以先求出
a
n
a_n
an，因为
z
z
z 都是质数，因此可以倒推出所有
a
i
a_i
ai。
z
z
z 不同的生成器之间不能倒推，但是可以开一个
O
(
k
)
O(k)
O(k) 的数组记录每个生成器最后生成的
a
a
a 是多少。
妙啊
代码
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long LL;
const int maxk=1e5+5;
int n,m,k,c[maxk],x[maxk],y[maxk],z[maxk],invx[maxk];
LL a,fn[maxk];
LL Pow(LL x,LL y,LL mo)
{
LL re=1;
for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
return re;
}
int main()
{
scanf("%d %d",&n,&m);
scanf("%lld %d",&a,&k);
fn[0]=a;
fo(i,1,k)
{
scanf("%d %d %d %d",&c[i],&x[i],&y[i],&z[i]);
invx[i]=Pow(x[i],z[i]-2,z[i]);
fo(j,1,c[i]) a=(x[i]*a+y[i])%z[i];
fn[i]=a;
}
int ans=0;
fd(i,k,1)
{
a=fn[i];
fo(j,1,c[i])
{
if (m==0) break;
if (a<m) m--, n--;
else if (n==m) ans++, n--, m--;
else n--;
a=(a-y[i]+z[i])*invx[i]%z[i];
}
}
a=fn[0];
if (a<m) m--, n--;
else if (n==m) ans++, n--, m--;
else n--;
printf("%d\n",ans);
}