【XVIII Open Cup E.V. Pankratiev. Grand Prix of Gomel E】Exit Song 题解

题目大意

  电影院观众席为 $n \times m$ 的方阵，其中 $k$ 个座位 $(r_1,s_1),\cdots,(r_k,s_k)$ 已经被占。问从剩下的座位中，选择某一行的一个连续段（长度至少为 $1$）的方案数。

  $n,m \leq 10^5,\ \ 1 \le k \le nm$，给定 $r_1,s_1,a_r,b_r,a_s,b_s$，按如下方式生成剩余数据：

$$r_i = (r_{i-1} \cdot a_r + b_r) \bmod n \\ s_i = (s_{i-1} \cdot a_s + b_s) \bmod m$$

  2s

题解

  它说它是数据随机生成，它可不是随机生成的啊，一次函数，模 $n$，后来它说 $k$ 是 $O(nm)$ 的，看来是 有 循 环 节

  这个 $r$ 和 $s$ 显然是有循环节的。为了方便处理，先把还没进入循环节的坐标（$(r_i,s_i)$ 横纵坐标任意一个没有进入循环节就算这个坐标没有进入循环节）特殊标记出来（怎么用后面再说）。假设去掉这些坐标以后，起始坐标为 $(r_0,s_0)$，$r$ 序列的循环节长度为 $pr$，循环节为 $r_0,\cdots,r_{pr-1}$；$s$ 序列的循环节长度为 $ps$，循环节为 $s_0,\cdots,s_{ps-1}$。
  这里会有 $pr \le n,\ ps \le m$。

  对于 $r_0$，暴力把这一行的所有纵坐标求出来（即 $s_0,s_{pr \bmod ps},s_{2pr \bmod ps},\cdots$，直到超出 $k$ 的限制），这个时间是 $O(\frac{ps}{\gcd(pr,ps)})$ 的。求出来之后丢进一个 set 里，就可以维护出这一行的答案了（记得考虑没进循环节的特殊点）。
  接下来最最重要的就是，发现有些行跟它是相似的！
  考虑第 $r_{ps \bmod pr}$ 行，发现它的纵坐标序列跟 $r_0$ 的纵坐标序列大体相同，只有头尾有些不同。（因为纵坐标的循环节就是 $ps$，所以中间大部分纵坐标循环了一圈没有变化，不同的在于，$r0$ 的最后几个纵坐标放到 $r_{ps \bmod pr}$ 里去可能超出了 $k$ 的限制，$r_{ps\bmod pr}$ 可能在开头会比 $r_0$ 多几个。）
  而头尾这些不同的元素数量是 $O(\lceil \frac{ps}{pr} \rceil)$ 的，可以用 $O(\lceil \frac{ps}{pr} \rceil)$ 的时间把 set 调整过来。
  同理，第 $r_{2ps \bmod pr}$ 行跟第 $r_{ps \bmod pr}$ 行也是这样相似的，第 $r_{3ps \bmod pr}$ 跟第 $r_{2ps \bmod pr}$ 行也是这样相似的……
  因此 $r_0,\cdots,r_{pr-1}$ 共分成了 $\gcd(ps,pr)$ 个相似类，每个相似类的大小为 $\frac{pr}{\gcd(ps,pr)}$。每个相似类首先暴力求出初始一行的纵坐标序列，丢进 set 里，然后遍历这个相似类，调整 set 算答案。
  暴力求初始纵坐标的时间复杂度为 $O(\gcd(ps,pr) \cdot \frac{ps}{\gcd(ps,pr)}) = O(ps)$，set 调整的次数为 $O(pr \cdot \lceil \frac{ps}{pr} \rceil) = O(ps)$，再加上 set 那么这题的复杂度就是 $O(m \log m)$。

代码

#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;

int n,m,r0,s0,ar,br,as,bs;
LL k;

int visr[maxn],viss[maxn],r[maxn],s[maxn],pr,ps;
vector<int> spc[maxn];
void make_period()
{
	while (k && (!visr[r0] || !viss[s0]))
	{
		spc[r0].push_back(s0);
		visr[r0]=1, viss[s0]=1;
		r0=(r0*(LL)ar+br)%n;
		s0=(s0*(LL)as+bs)%m;
		k--;
	}
	
	memset(visr,0,sizeof(visr));
	for(; !visr[r0]; r0=(r0*(LL)ar+br)%n) visr[r0]=1, r[pr++]=r0;
	memset(viss,0,sizeof(viss));
	for(; !viss[s0]; s0=(s0*(LL)as+bs)%m) viss[s0]=1, s[ps++]=s0;
}

inline LL sum1(LL x) {return (x*(x+1))>>1;}

LL ans1,ans;
set<int> S;
void add(int x)
{
	int l,r;
	set<int>::iterator it=S.upper_bound(x);
	r=*it;
	it--;
	l=*it;
	ans1+=sum1(x-l-1)+sum1(r-x-1)-sum1(r-l-1);
	S.insert(x);
}
void del(int x)
{
	int l,r;
	set<int>::iterator it=S.lower_bound(x);
	it--;
	l=*it;
	it++;it++;
	r=*it;
	it--;
	ans1+=sum1(r-l-1)-sum1(x-l-1)-sum1(r-x-1);
	S.erase(it);
}
void calc_ans(int i)
{
	for(int x:spc[i]) add(x);
	ans+=ans1;
	for(int x:spc[i]) del(x);
}

int main()
{
	scanf("%d %d %lld",&n,&m,&k);
	scanf("%d %d %d",&r0,&ar,&br);
	scanf("%d %d %d",&s0,&as,&bs);
	
	make_period();
	
	memset(visr,0,sizeof(visr));
	memset(viss,0,sizeof(viss));
	int timeStamp=0;
	fo(i,0,pr-1) if (!visr[r[i]])
	{
		timeStamp++;
		ans1=sum1(m);
		S.clear();
		S.insert(-1), S.insert(m);
		deque<int> Q;
		LL curTime=i+1;
		for(int j=i%ps; curTime<=k; (j+=pr)%=ps, curTime+=pr)
		{
			if (viss[j]==timeStamp) break;
			Q.push_back(j);
			viss[j]=timeStamp;
			add(s[j]);
		}
		
		for(int ii=i; !visr[r[ii]]; (ii+=ps)%=pr)
		{
			visr[r[ii]]=1;
			if (Q.empty())
			{
				curTime=ii+1;
				for(int j=ii%ps; curTime<=k; (j+=pr)%=ps, curTime+=pr)
				{
					Q.push_back(j);
					add(s[j]);
				}
			} else
			{
				while (Q.front()!=ii%ps)
				{
					int j=((Q.front()-pr)%ps+ps)%ps;
					add(s[j]);
					Q.push_front(j);
				}
			}
			while (!Q.empty() && ii+1+(Q.size()-1)*(LL)pr>k)
			{
				del(s[Q.back()]);
				Q.pop_back();
			}
			calc_ans(r[ii]);
		}
	}
	ans1=sum1(m);
	S.clear();
	S.insert(-1), S.insert(m);
	fo(i,0,n-1) if (!visr[i]) calc_ans(i);
	
	printf("%lld\n",ans);
}