数论
矩阵快速幂 [NOI2012] 随机数生成器
这道题递推公式已经给我们了
\[X_{n+1}=(aX_n+c) \bmod m \]但是如果用这个递推式如果直接使用的会超时，所以我们用矩阵快速幂来优化
首先我们构造初始矩阵：\(\begin{bmatrix}X_{i-1} & c\end{bmatrix}\)
根据递推式我们可以知道
\[X_i=X_{i-1}\times a+c\times 1\\ c=X_{i-1}\times0+c \times1 \]所以矩阵转移为
\[X_n=\begin{bmatrix} a & 0\\ 1 & 1 \end{bmatrix} \times\begin{bmatrix}X_{i-1} & c\end{bmatrix} \]#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5;
LL mod, go, c, x, n, g;
struct node
{
LL m[N][N];
} a, mm;
LL quick_mul(LL x, LL y)
{
long long ans = 0;
while (y != 0)
{
if (y & 1)
ans = (ans + x) % mod;
y >>= 1;
x = (x << 1) % mod;
}
return ans;
}
node Mul(node x, node y)
{
node c;
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= 2; j++)
c.m[i][j] = 0;
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= 2; j++)
for (int k = 1; k <= 2; k++)
c.m[i][j] += quick_mul(x.m[i][k] % mod, y.m[k][j] % mod), c.m[i][j] %= mod;
return c;
}
void qpow(LL p)
{
while (p)
{
if (p & 1)
a = Mul(a, mm);
mm = Mul(mm, mm);
p >>= 1;
}
}
int main()
{
cin >> mod >> go >> c >> x >> n >> g;
memset(a.m, 0, sizeof(a.m));
memset(mm.m, 0, sizeof(mm.m));
a.m[1][1] = x, a.m[1][2] = c;
mm.m[1][1] = go, mm.m[2][1] = mm.m[2][2] = 1;
qpow(n);
cout << a.m[1][1] % g;
return 0;
}
P2233 [HNOI2002] 公交车路线
这道题其实我们也可以用 \(\text {dp}\) 来处理
我们设 \(f_{i,j}\) 为第 \(i\) 站在 \(j\) 次乘坐后到达的方案数
边界 \(f_{0,0}=1\)
因为我们每次只能从相邻位置转移过来，所以转移方程为
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1} \]我们发现每一个状态都至只与上一个状态有关，所以我们将数组可以压位为 \(f_{4,2}\)
我们分成 \(4\) 次状态转移
\[f_{0,t}=2\times f_{1,t \oplus1}\bmod1000 \enspace\text{因为A处的方案等于两边的方案相加} \]\[f_{1,t}=(f_{0,t\oplus1}+f_{2,t\oplus1}) \]\[f_{2,t}=(f_{1,t\oplus1}+f_{3,t\oplus1})\enspace\text{两个都是前面和后面的方案相加} \]\[f_{3,t}=f_{2,t\oplus1}\enspace\text{D只能由C来,因为到了E便不能回头} \]#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9')
{
if (s == '-')
f = -f;
s = getchar();
}
while (s >= '0' && s <= '9')
{
x = (x << 3) + (x << 1) + (s ^ 48);
s = getchar();
}
return x * f;
}
const int MOD = 1000;
int f[4][2];
int n, t = 0;
int main()
{
f[0][0] = 1;
n = read();
for (int i = 1; i < n; i++)
{
t ^= 1;
f[0][t] = 2 * f[1][t ^ 1] % MOD;
f[1][t] = (f[0][t ^ 1] + f[2][t ^ 1]) % MOD;
f[2][t] = (f[1][t ^ 1] + f[3][t ^ 1]) % MOD;
f[3][t] = f[2][t ^ 1];
}
cout << 2 * f[3][t] % MOD;//E由D和F来
return 0;
}