【Samara Farewell Contest 2020 H】Video Reviews - 2 题解

题目大意

  有 $n$ 个人排队准备录视频，轮到第 $i$ 个人的时候，如果他被商家钦定，或者排他前面的至少有 $a_i$ 个人录视频，他就会录视频。问商家至少钦定多少人，使得最终录视频的人数 $\ge m$。
  $m \le n \le 5 \times 10^7$，由于输入过大，仅输入 $a_1$，接下来给出 $k$ 段生成器，每段生成 $c_i$ 个 $a$（保证 $\sum_{i=1}^k c_i=n-1$），每个生成器形如 $a_i=(x a_{i-1}+y) \bmod z$，$z$ 为质数。
  $k \le 10^5$
  4s, 64MB

题解

  思考许久，转头发现，这个空间，甚至连 $n$ 的数组都存不下。。。

  感觉题解给得很妙啊。

  考虑最后一个人，如果 $a_n < m$，他是一定会录视频的，因此转化为子任务 $(n-1,m-1)$；
  否则，如果 $a_n \ge m$ 且 $n=m$，这个人必须被钦定，不然不合法，因此也转化为子任务 $(n-1,m-1)$；
  否则，$a_n \ge m$ 且 $n > m$，此时要么前 $n-1$ 个人已经选出了 $m$ 个，那么第 $n$ 人直接扔了就好；要么前 $n-1$ 个人只选了 $m-1$ 个，想要钦定第 $n$ 个人，但是钦定前面的人只会使答案更优，所以不会有该情况。也就是说，$a_n \ge m$ 且 $n > m$ 时，直接忽略最后一个人，转化为子任务 $(n-1,m)$。

  于是这样倒着做一遍就做好了。

  由于空间不允许存下整个数组，可以先求出 $a_n$，因为 $z$ 都是质数，因此可以倒推出所有 $a_i$。$z$ 不同的生成器之间不能倒推，但是可以开一个 $O(k)$ 的数组记录每个生成器最后生成的 $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);
}