【2023 NOI 模拟赛 01】膜 做题记录

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,… ,a_n$，令 $f(x,n)= x\ mod\ a_n,f(x, i) =(x\ mod\ a_i)+ f(x\ mod\ a_i,i+ 1)$。

求 $x$ 为非负整数时，$f(x,1)$ 的最大值。

$1\le n\le 2\times 10^5$，$1\le a_i\le 10^{13}$。

记 $x_i=x\mod a_1\mod a_2\mod\dots\mod a_i$，$ans_i=f(x)-f(x_i,i+1)$ 也就是前缀和。

设状态 $(i,r,S)$ 表示考虑了 $a_{[1,i]}$，$x_i\in[0,r]$ 且 $ans_i=ix_i+S$，那么显然这个状态下最大的 $ans_i$ 为 $ir+S$。

这是图解，最大的 $ans_i$ 即为 $i$ 前面那个楼梯的面积：

考虑转移，有两种情况：

• $r\le a_{i+1}$：无事发生，转移到 $(i+1,r,S)$；

• $r>a_{i+1}$：需要取模，分成两种子情况：

  

  • $x_i\le r-(r\mod a_{i+1})$：蓝色部分，转移到 $(i+1,a_{i+1}-1,S+i(r-(r\mod a_{i+1})-a_{i+1})$；
  • $x_i> r-(r\mod a_{i+1})$：红色部分，转移到 $(i+1,r\mod a_{i+1},S+i(r-(r\mod a_{i+1}))$；

  图解（绿色是第一种转移 $S$ 增加的部分，黄色是第二种）:

  

不难发现，第二种转移的 $r$ 是固定的，那么只需要将 $S$ 取 $\max$ 即可，所以每个 $i$ 最多只会贡献一种新状态，并且由于最多取模 $\log V$ 次（$V$ 是值域），所以状态数是 $n\log V$ 的，用 set 优化转移可以做到 $O(n\log V+n\log(n\log V))$ 的时间复杂度。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int S=200005;

inline void fio(string name)
{
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

struct node
{
	long long r,s;
	inline bool operator<(node b) const
	{
		return r==b.r?s>b.s:r>b.r;
	}
};

int n,m;
long long a[S];
set<node> dp;

int main()
{
	fio("mod");
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	dp.insert((node){a[1]-1,0});
	for(int i=2;i<=n;i++)
	{
		long long mx=-114;
		for(node u:dp)
		{
			if(u.r<a[i]) break;
			dp.insert((node){u.r%a[i],u.s+(i-1)*(u.r-u.r%a[i])}); 
			mx=max(mx,u.s+(i-1)*(u.r-u.r%a[i]-a[i]));
		}
		while((*dp.begin()).r>=a[i]) dp.erase(dp.begin());
		if(mx!=-114) dp.insert((node){a[i]-1,mx});
	}
	long long ans=0;
	for(node u:dp) ans=max(ans,n*u.r+u.s);
	printf("%lld\n",ans);
	return 0;
}