【2019 Multi-University 4 I】Linear Functions 题解

题目大意

  有 $n$ 个元素，第 $i$ 个元素在初始 $0$ 时刻时值为 $a_i$，此后每个时刻增加 $b_i$ 并模 $p_i$，即在 $t$ 时刻时值为 $(a_i+b_i\cdot t) \bmod p_i$，其中 $t$ 为整数。
  求

$$\max_{t=0}^T \{\sum_{i=1}^n (a_i+b_i\cdot t) \bmod p_i \}$$

  输出这个最大值，及其对应的最早的时刻。

  $1 \leq n,T \leq 10^5,\ \ 0 \leq a_i,b_i < p_i,\ \ 5\times10^8 < p_i < 10^9$
  多测，$\sum n \leq 10^6$，80% 数据保证 $n \leq 1000$
  保证 $p_i$ 为质数；
  $a_i,b_i$ 在 $[0,p_i)$ 范围内随机生成；
  5s

$$\\$$ $$\\$$ $$\\$$

题解

  鉴于目前这题只有两篇不讲人话的题解（官方题解和 Zayin 的博客），我决定补掉这题并写一篇世人能看得懂的题解

  首先思考一些比较暴力的做法，一开始令 $ans=\sum_{i=1}^n a_i$，然后每往后走一个时刻默认给 $ans$ 加上 $\sum_{i=1}^n b_i$，然后我们对于每个 $i$ 事先标记出哪些时刻要让 $ans-=p_i$，这样就可以算出答案了。
  这样乍一看是 $O(nT)$ 的，但写准确一点应该是 $O(n\lfloor\frac{b_iT}{p_i}\rfloor)$ 的，因为 $-p_i$ 的标记只有 $\lfloor\frac{a_i+b_iT}{p_i}\rfloor$ 个，因此单个 $i$ 的预处理是 $O(\lfloor\frac{b_iT}{p_i}\rfloor)$ 的。
  这在 $b_i$ 小的时候很好，在 $b_i$ 大的时候（接近 $p_i$ 的时候）就变成 $O(nT)$ 了。

  所以接下来要用一些姿势，使得 $b_i$ 能够变小。

  举个例子观察一下，比如 $b_i=4,~p_i=11$，那么 $(b_i\cdot t)~\text{mod}~p_i$ 会长这个样子：

$$4,8,1,5,9,2,6,10,3,7,0,4,\cdots$$

  记 $G=\lfloor \sqrt n \rfloor$，比如我们假设 $G=4$，那么观察前 $4$ 个数，记 $stp$ 表示这前 $G$ 个数的最小值，$g$ 表示最小值在第几个取到。（这个例子中 $stp=1,~g=3$）
  把时间 $t$ 按模 $g$ 分组，则可以发现，这个数列分成了 $g$ 组，每组起始值不同，间隔都是 $stp$，并且 $stp$ 比较小。

  $stp$ 有多小呢？在 $b_i$ 随机的情况下是 $O(\frac{p_i}{G})$ 的。这里引用一下 Zayin 的粗略证明：

  粗略证明（其实严格的我也不会….)
  当 $a$ 很大（比如 $a>\frac pk$）时，$a,2a\%p,3a\%p\cdots ka\%p$ 这个数列几乎可以认为是随机的，而在 $[0,p)$ 中随机选 $k$ 个数的最小值的期望是 $\frac P{k+1}$
  当 $a$ 很小（比如 $a<\frac pk$）时，$a,2a\%p,3a\%p\cdots ka\%p$ 等价于 $a,2a,3a\cdots ka$（因为 $a$ 很小），所以最小值的期望是 $a$，而此时 $a$ 的期望则是 $\frac p{2k}$。
  所以 $a,2a\%p,3a\%p\cdots ka\%p$ 是 $\frac pk$ 这个量级的。
  而根据程序验证，最小值大都处于 $[\frac pk,\frac {2p}k]$ 之间，相对来说比较符合。

  那么现在尝试用 $stp$ 代替 $b_i$ 来压时间。就是说现在有了一个 $g$ 和 $stp$，那么把时间按模 $g$ 分组，每组独立做。原来的时候，第 $i$ 个元素在 $t$ 时刻的贡献为 $a_i+b_i \cdot t-\lfloor \frac{a_i+b_i \cdot t}{p_i} \rfloor p_i$，现在相当于把 $a_i$ 换成了相应的初值，把 $b_i$ 换成了 $stp$，$t$ 压缩成从 $0$ 到 $\frac T{g}$。
  然后每组还是按照一开始那个暴力做法来做，即每个时刻默认加 $stp$，然后用 $O(\lfloor \frac{stp \cdot \frac T{g}}{p_i} \rfloor)$ 的时间来打 $-p_i$ 标记预处理。

  这样一来，单个 $i$ 的打标记复杂度变成 $O(g\lfloor \frac{stp\cdot \frac Tg}{p_i} \rfloor)=O(g\lfloor \frac{\frac{p_i}{\sqrt n}\cdot \frac T{g}}{p_i} \rfloor)=O(\frac T{\sqrt n})$，因此 $n$ 个元素打标记总复杂度为 $O(T\sqrt n)$。
  然后扫一遍时间算答案的这部分，$g$ 相同的元素可以放一起扫，只有 $\sqrt n$ 种不同的 $g$，因此这部分总时间为 $O(\sqrt n \cdot g \frac Tg)=O(T\sqrt n)$。
  因此总时间是 $O(T \sqrt n)$。

  UPD：然后这题要卡常。
  这题主要的卡常姿势是：在上面我们是正着走的，即 $stp=(b_i \cdot t)~\text{mod}~p_i$，我们再加上个倒着走，即 $stp=-(p_i-b_i) \cdot t~\text{mod}~p_i$ 也拿来比较一下。这样可以优化掉一半的时间。
  然后注意把 long long 换成 int。

参考

  Zayin 的博客：https://blog.csdn.net/Zayin___/article/details/100529778

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=1e5+5, maxsqrtn=500;

int n,T,a[maxn],b[maxn],p[maxn],sqrtn,stp[maxn],sig[maxn];
LL Ans[maxn];

void ReadInt(int &data)
{
	data=0;
	char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	do{
		data=(data<<3)+(data<<1)+ch-'0';
		ch=getchar();
	} while (ch>='0' && ch<='9');
}

inline void add(int &now,const int &b,const int &p)
{
	now+=b;
	now=(now>=p) ?now-p :now;
}

vector<int> v[maxsqrtn];
LL tag[maxn];
int main()
{
	while (scanf("%d %d",&n,&T)!=EOF)
	{
		fo(i,1,n) ReadInt(a[i]);
		fo(i,1,n) ReadInt(b[i]);
		fo(i,1,n) ReadInt(p[i]);
		
		fo(i,0,T) Ans[i]=0;
		
		sqrtn=sqrt(n);
		fo(i,1,sqrtn) v[i].clear();
		fo(i,1,n)
		{
			stp[i]=p[i]+5;
			int now=0, g;
			fo(j,1,sqrtn)
			{
				add(now,b[i],p[i]);
				if (now<stp[i]) stp[i]=now, g=j, sig[i]=1;     //正着走
				if (p[i]-now<stp[i]) stp[i]=p[i]-now, g=j, sig[i]=-1;     //倒着走
			}
			v[g].push_back(i);
		}
		fo(g,1,sqrtn)
		{
			fo(i,0,T) tag[i]=0;
			LL sumstp=0;
			
			for(int i:v[g])
			{
				sumstp+=stp[i]*sig[i];
				for(int j=0, st=a[i]; j<g; j++, add(st,b[i],p[i]))
				{
					tag[j]+=st;
					if (stp[i]==0) continue;
					for(int now=st, t=j, tmp, nextt; ; t=nextt)
					{
						tmp=(sig[i]==1) ?(p[i]-1-now)/stp[i]+1 :now/stp[i]+1 ;
						if (t+(LL)tmp*g>T) break;
						nextt=t+tmp*g;
						tag[nextt]-=p[i]*sig[i];
						now+=(tmp*stp[i]-p[i])*sig[i];
					}
				}
			}
			fo(i,g,T) tag[i]+=tag[i-g]+sumstp;
			
			fo(i,0,T) Ans[i]+=tag[i];
		}
		
		int w=0;
		fo(i,1,T) if (Ans[i]>Ans[w]) w=i;
		
		printf("%lld %d\n",Ans[w],w);
	}
}