P6202 [USACO07CHN]Summing Sums G
Dehydration
·
·
题解
前言：
简单的矩阵乘法。
ps：题目。
思路：
令原数和加密后的数构成一个矩阵，设矩阵 A 为
推出 $A$ 乘矩阵 $\begin{bmatrix}0&n-1\\1&n-2\end{bmatrix}$ 可以得到 $A'$，设这个矩阵为 $B$。
按照这个规律，加密 $T$ 次和 $T+1$ 次构成的矩阵为 $A\times B^T$。
对于每个数，处理出矩阵 $A$，就可以用快速幂解决 $A\times B^T$，得到加密 $T$ 次的数。
**记住，不开 long long 见祖宗！！！**
### 代码：
```
#include <bits/stdc++.h>
#define MOD 98765431
typedef long long lint;
struct matrix
{
int x , y;
lint num[3][3];
matrix operator*(const matrix a) const
{
matrix t;
int i , j , k;
memset(t.num , 0 , sizeof(t.num));
t.x = x , t.y = a.y;
for(i = 1 ; i <= t.x ; i ++ )
for(j = 1 ; j <= t.y ; j ++ )
for(k = 1 ; k <= y ; k ++ )
t.num[i][j] = (t.num[i][j] + num[i][k] * a.num[k][j]) % MOD;
return t;
}
}a , b;
lint c[50010];
matrix qpow(matrix a , int b)
{
matrix t;
int i;
t.x = a.x , t.y = a.y;
memset(t.num , 0 , sizeof(t.num));
for(i = 1 ; i <= t.x ; i ++ )
t.num[i][i] = 1;
while(b)
{
if(b & 1)
t = t * a;
a = a * a;
b >>= 1;
}
return t;
}
typedef long long LL;
inline LL read()
{
register LL x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int main()
{
int n , t , i;
lint sum = 0;
n=read(),t=read();
for(i = 1 ; i <= n ; i ++ )
c[i]=read() , sum = (sum + c[i]) % MOD;
b.x = b.y = 2;
b.num[1][1] = 0 , b.num[1][2] = n - 1 , b.num[2][1] = 1 , b.num[2][2] = n - 2;
b = qpow(b , t);
a.x = 1 , a.y = 2;
for(i = 1 ; i <= n ; i ++ )
{
a.num[1][1] = c[i] , a.num[1][2] = (sum - c[i] + MOD) % MOD;
printf("%lld\n" , (a * b).num[1][1]);
}
return 0;
}//别问我为什么要加快输，因为我要最优解
```
~~要看就看我的，我是最优解呢~~
c++14 + O2 = 最优解。