超强记忆
- $Time limit:3500ms$
- $Memory limit:2MiB$
请各位选手特别注意本题时间限制与空间限制。
题目背景
在《最强大脑》上，经常能看到那些有着超强记忆能力的人。
那天小明与小红心血来潮，也想玩玩这个游戏。然而，两人都是会作弊的。
小明拿出了他新写的程序，准备一一记下小红报出数字。
小红拿出了她的“随机”数据生成器，准备随机生成 $n$ 个数字 $a_i$，并随机生成 $q$ 个位置 $p_i$ 让小明回答 $a_{p_i}$ 是多少。
结果小红一不小心把 $n$ 和 $q$ 搞大了，小明的程序爆了……小红懒得改了，你能帮帮小明吗？
输入格式
由于本题输入数据量过大，题目数据以特殊方式生成。
第一行五个正整数 $n,q,seed,x,y$，$n$ 表示数字的个数，其余为数据生成参数。
$a_i,p_i$ 的生成方式由以下代码给出：
const int mod = 1000000007;
int n, q, seed, x, y;
int a[50000001];
int p[50000001];
int nxt(){
return seed = (1ll * x * seed + y) % mod;
}
void init(){
scanf("%d%d%d%d%d", &n, &q, &seed, &x, &y);
for(int i = 1; i <= n; i++)
a[i] = nxt();
for(int i = 1; i <= q; i++)
p[i] = nxt() % n + 1;
}若需要，并且建议修改此代码，只要修改此代码后，程序运行结果一致，则仍然可以通过。
输出格式
由于本题输出数据量过大，故本题采用特殊输出方式。
你需要输出一行一个整数，表示 $\sum\limits_{i=1}^qia_{p_i} \pmod {10^9+7}$。
输入数据 1
1 1 2 5 9输出数据 1
19$a_1=19$，查询 $a_1$。
输入数据 2
5 5 3 7 10输出数据 2
193133$a=[31,227,1599,11203,78431]$，查询 $a_3,a_5,a_4,a_2,a_1$。
数据范围
对于 $100\%$ 的数据，$1\le n,q\le 5\times10^7,0\le seed,x,y<10^9+7$。
请各位选手特别注意本题时间限制与空间限制。
题解
这道题显然问题出在脑子不够用（物理）
我们不能把“随”出来的$a_i$存住来查询，那么我们只能先把$seed$处理到查询部分，然后再根据我们每次要查询的下标返回去递推算值。
虽然空间解决了，但是时间是没话说，炸透了。
每次算值都是一步步的做重复的线性变换，那我们有没有办法加速这个过程呢？
我选择讲矩阵快速幂的做法
接触过线性代数的同学知道，一个矩阵乘上一个向量就是相当于对向量做一个线性变换。
$$ \begin{bmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{bmatrix} \cdot \begin{bmatrix} b_{1} \\ b_{2} \end{bmatrix} = \begin{bmatrix} a_{1,1}b_{1}+a_{1,2}b_{2} \\ a_{2,1}b_{1}+a_{2,2}b_{2} \end{bmatrix} $$
而我们的递推式正好就是一个线性变换，通过凑数法可得：
$$ \begin{bmatrix} x & y \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} seed \\ 1 \end{bmatrix} = \begin{bmatrix} x\cdot seed+y\cdot 1 \\ 0\cdot x+1\cdot 1 \end{bmatrix} = \begin{bmatrix} x\cdot seed+y \\ 1 \end{bmatrix} $$
这样我们就递推了一次得到第一项。
那我们想知道第i项的话，我们就在他前面乘上$i$次：
$$ \begin{bmatrix} seed_i \\ 1 \end{bmatrix} = \left ( \begin{bmatrix} x & y \\ 0 & 1 \end{bmatrix} \times \cdots \times \left ( \begin{bmatrix} x & y \\ 0 & 1 \end{bmatrix} \times \left ( \begin{bmatrix} x & y \\ 0 & 1 \end{bmatrix} \times \left ( \begin{bmatrix} x & y \\ 0 & 1 \end{bmatrix} \times \begin{bmatrix} seed \\ 1 \end{bmatrix} \right ) \right ) \right )\cdots \right ) $$
好消息是，矩阵乘法符合结合律，所以可以直接写成：
$$ \begin{bmatrix} seed_i \\ 1 \end{bmatrix} = \begin{bmatrix} x & y \\ 0 & 1 \end{bmatrix}^i \cdot \begin{bmatrix} seed \\ 1 \end{bmatrix} $$
既然矩阵乘法也符合结合律，那就能用快速幂。
本来是可以的，但模运算太多，导致$O(nlogn)$的做法被卡掉了（悲）
于是，就出现了 “光速幂”
因为底数相同是$\begin{bmatrix}x & y\\ 0 & 1\end{bmatrix}$，那么就可以预处理。虽然做不到全部预处理，但是可以根号分治
把要算的$\begin{bmatrix}x & y\\ 0 & 1\end{bmatrix}^i$直接变成$\begin{bmatrix}x & y\\ 0 & 1\end{bmatrix}^{i-i\%10000}\cdot \begin{bmatrix}x & y\\ 0 & 1\end{bmatrix}^{i\%10000}$
那么，预处理$10000$以内的数和整万数就好了，覆盖$10^8$范围，空间复杂度$O(4\cdot 2\cdot 10000)$
时间直降为$O(q)$
$code:$
#include<cstdio>
using namespace std;
const int mod = 1000000007;
int n,q,seed,x,y;
int nxt(){return seed=(1ll*x*seed+y)%mod;}
int ans=0,cnt=0;//算答案的，这个式子拆不了
void add(int api){ans=(ans+((1ll)*(++cnt)*api)%mod)%mod;}
struct matrix2{
int a11,a21;
};
struct matrix{//重载运算符很香
int a11,a12,a21,a22;
matrix operator *(const matrix &x)const{
matrix ret;
ret.a11=((1ll)*a11*x.a11%mod+(1ll)*a12*x.a21%mod)%mod;
ret.a12=((1ll)*a11*x.a12%mod+(1ll)*a12*x.a22%mod)%mod;
ret.a21=((1ll)*a21*x.a11%mod+(1ll)*a22*x.a21%mod)%mod;
ret.a22=((1ll)*a21*x.a12%mod+(1ll)*a22*x.a22%mod)%mod;
return ret;
}
matrix2 operator *(const matrix2 &x)const{
matrix2 ret;
ret.a11=((1ll)*a11*x.a11%mod+(1ll)*a12*x.a21%mod)%mod;
ret.a21=((1ll)*a21*x.a11%mod+(1ll)*a22*x.a21%mod)%mod;
return ret;
}
};
matrix base;//矩阵幂的基底
matrix pre1[10001];//预处理万内
matrix pre2[10001];//预处理整万
matrix e={1,0,0,1};//单位矩阵
void init(){
pre1[0]=pre2[0]=e;//单位矩阵就像数字中的1一样
for(int i=1;i<=10000;i++){
pre1[i]=pre1[i-1]*base;
}
for(int i=1;i<=10000;i++){
pre2[i]=pre2[i-1]*pre1[10000];
}
}
matrix qpow(int b){//光速幂
if(b<=10000)return pre1[b];
else return pre2[b/10000]*pre1[b%10000];
return e;//不返回会CE
}
signed main(){
scanf("%d%d%d%d%d", &n, &q, &seed, &x, &y);
base={x,y,0,1};
init();//预处理
matrix2 seed_m=(matrix2){seed,1};//保种
seed=(qpow(n)*seed_m).a11;
int qry;
for(int i=1;i<=q;i++){
qry=nxt()%n+1;//这个虽然模很慢，但已经不能优化了
add((qpow(qry)*seed_m).a11%mod);//最后右边乘上要变换的向量
}
printf("%d",ans);
return 0;
}