题解 P5343 【【XR-1】分块】
ztyqwq
·
·
题解
本蒻蒟比赛的时候想不到简单的方法，于是只能死守DP.
首先是处理读入的两行数据，去重。同样只想到了用unique的很暴力的处理手段：
scanf("%lld", &n);
scanf("%lld", &pr);
for(ll i = 1; i <= pr; i++) scanf("%lld", &ava1[i]);
scanf("%lld", &nf);
for(ll i = 1; i <= nf; i++) scanf("%lld", &ava2[i]);
sort(ava1 + 1, ava1 + pr + 1, cmp);
sort(ava2 + 1, ava2 + nf + 1, cmp);
ava1[0] = unique(ava1 + 1, ava1 + pr + 1) - ava1 - 1;
ava2[0] = unique(ava2 + 1, ava2 + nf + 1) - ava2 - 1;
for(int i = 1; i <= ava1[0]; i++) ava[i] = ava1[i];
for(int i = 1; i <= ava2[0]; i++) ava[i + ava1[0]] = ava2[i];
sort(ava + 1, ava + ava1[0] + ava2[0] + 1, cmp);
for(ll i = 1; i <= ava1[0] + ava2[0]; i++)
if(ava[i] == ava[i - 1] && ava[i + 1] != ava[i])
ava[++ava[0]] = ava[i];
但这都不是重点,重点是怎么计算左右分块方案，很明显qwq，这道题类似爬楼梯，所以直接暴力转移：
f[i]\text{ 表示到长度 }i\text{ 一共有多少可能的分块数量。}
f[i] = \sum^{ava[0]}_{i = 1}f[i - ava[i]]
显然。
for(int i = 1; i <= n; i++)
for(int j = 1; j <= ava[0]; j++)
f[i] = (f[i] + f[i - ava[j]]) % MOD;
但是这只能过60%的数据...
一看100%的数据规模
1 \leq n \leq 10^{18}
...
...
...
所以我们需要优化qwq
## 矩阵
$$\left[ \begin{array} { c c c c } { a _ { 11 } } & { a _ { 12 } } & { \cdots } & { a _ { 1 n } } \\ { a _ { 21 } } & { a _ { 22 } } & { \cdots } & { a _ { 2 n } } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { a _ { n 1 } } & { a _ { n 2 } } & { \cdots } & { a _ { n n } } \end{array} \right]$$
矩阵满足的运算有加法，减法，乘法和其他一些...
但是我们关注的是矩阵乘法。矩阵的乘法是有条件的，如果两个矩阵A和B，那么只有当A的列数和B的行数相同时才可以乘法，乘法满足：
设$A$为$m \times p$的矩阵，$B$为$p \times n$的矩阵，那么称$m \times n$的矩阵C为矩阵A与B的乘积，记作$C=AB$ ，其中矩阵$C$中的第$i$行第$j$列元素可以表示为：
$$( A B ) _ { i j } = \sum _ { k = 1 } ^ { p } a _ { i k } b _ { k j } = a _ { i 1 } b _ { 1 j } + a _ { i 2 } b _ { 2 j } + \cdots + a _ { i p } b _ { p j }$$
举个栗子：
$$C = A B = \left( \begin{array} { l l l } { 1 } & { 2 } & { 3 } \\ { 4 } & { 5 } & { 6 } \end{array} \right) \left( \begin{array} { l l } { 1 } & { 4 } \\ { 2 } & { 5 } \\ { 3 } & { 6 } \end{array} \right) = \left( \begin{array} { c c } { 1 \times 1 + 2 \times 2 + 3 \times 3 } & { 1 \times 4 + 2 \times 5 + 3 \times 6 } \\ { 4 \times 1 + 5 \times 2 + 6 \times 3 } & { 4 \times 4 + 5 \times 5 + 6 \times 6 } \end{array} \right) = \left( \begin{array} { c c } { 14 } & { 32 } \\ { 32 } & { 77 } \end{array} \right)$$
而且重要的是矩阵满足结合律，分配律。
所以...
就做出来啦！
先举个小栗子，菲波那切数列：
$$f(i) = f(i - 1) + f(i - 2)$$
可以用递归或递推$O(n)$求出来，但如果我让你写$O(log n)$的算法，该怎么办呢？
矩阵就派上用场啦：
如果我有一个矩阵
$$\left[ \begin{array} { l } { f ( n - 1 ) } \\ { f ( n - 2 ) } \end{array} \right]$$
你能把它变成
$$\left[ \begin{array} { l } { f ( n ) } \\ { f ( n - 1 ) } \end{array} \right]$$
吗？
首先
$$\begin{aligned}
f(n) &= f(n - 1) + f(n - 2)\\
f(n - 1) &= f(n - 1)\\
\end{aligned}$$
所以不难发现，我们只要乘上一个矩阵就可以啦：
$$\left[ \begin{array} { l } { f ( n ) } \\ { f ( n - 1 ) } \end{array} \right] = \left[ \begin{array} { l l } { 1 } & { 1 } \\ { 1 } & { 0 } \end{array} \right] \left[ \begin{array} { l } { f ( n - 1 ) } \\ { f ( n - 2 ) } \end{array} \right]$$
代码实现：
```cpp
struct mat{
ll r, c;
ll m[MAXM][MAXM];
void clear(){memset(m, 0, sizeof(m));}
};
mat matMul(mat m1, mat m2){
mat ret;
ret.r = m1.r; ret.c = m2.c;
for(int i = 1; i <= ret.r; i++)
for(int j = 1; j <= ret.c; j++){
ll t = 0;
for(int k = 1; k <= m1.c; k++)
t = (t + (m1.m[i][k] * m2.m[k][j]) % MOD) % MOD;
ret.m[i][j] = t;
}
return ret;
}
```
但是一个一个程，复杂度还是$O(n)$的，甚至因为矩阵，复杂度常数变大了，那要这个玩意儿还有什么用？
嗯，看起来没用，所以...
等一下！矩阵满足交换结合律，而且$O(\log n)$怎么听起来这么像我们以前学过的一个叫内个什么算法：
$$\Large\text{快速幂}$$
隆重介绍：矩阵快速幂！！！
## 矩阵快速幂
我们乘上$n$个相同的矩阵，相当于$O(\log n)$求出该矩阵的$n$次方，随后再乘上初始值，即：
$$\left[ \begin{array} { l } { f ( n ) } \\ { f ( n - 1 ) } \end{array} \right] = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 1 } & { 0 } \end{array} \right] \left[ \begin{array} { c c } { f ( n - 1 ) } \\ { f ( n - 2 ) } \end{array} \right] = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 1 } & { 0 } \end{array} \right] ^ { 2 } \left[ \begin{array} { c c } { f ( n - 2 ) } \\ { f ( n - 3 ) } \end{array} \right] = \cdots = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 1 } & { 0 } \end{array} \right] ^ { n - 2 } \left[ \begin{array} { c } { f ( 2 ) } \\ { f ( 1 ) } \end{array} \right]$$
模板如下：
```cpp
mat qpow(mat x, ll powers){
mat ret; ret.clear(); ret.r = x.r; ret.c = x.c;
for(ll i = 1; i <= ret.r; i++)
ret.m[i][i] = 1;
while(powers){
if(powers & 1) ret = matMul(ret, x);
x = matMul(x, x);
powers >>= 1;
}
return ret;
}
```
要注意模板中的单位矩阵不是：
$$\left[ \begin{array} { c c c c } { 1 } & { 1 } & { \cdots } & { 1 } \\ { 1 } & { 1 } & { \cdots } & { 1 } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { 1 } & { 1 } & { \cdots } & { 1 } \end{array} \right]$$
单位矩阵应该是：
$$\left[ \begin{array} { c c c c } { 1 } & { 0 } & { \cdots } & { 0 } \\ { 0 } & { 1 } & { \cdots } & { 0 } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { 0 } & { 0 } & { \cdots } & { 1 } \end{array} \right]$$
自己乘一乘就知道了qwq。
扩大到最多100阶的“菲波那切数列”而已，也就很容易了。
矩阵第一行是你要加的位置为1，其余为0。剩余的是对角线为1，偏移1位。
AC代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXM = 110;
const ll MOD = 1e9 + 7;
ll n, pr, nf, ava1[MAXM], ava2[MAXM], ava[MAXM << 1 | 1], ans;
struct mat{
ll r, c;
ll m[MAXM][MAXM];
void clear(){memset(m, 0, sizeof(m));}
};
mat matMul(mat m1, mat m2);
void prt(mat m);
mat qpow(mat x, ll powers);
bool cmp(const ll &x, const ll &y){return x < y;}
int main(){
scanf("%lld", &n);
scanf("%lld", &pr);
for(ll i = 1; i <= pr; i++) scanf("%lld", &ava1[i]);
scanf("%lld", &nf);
for(ll i = 1; i <= nf; i++) scanf("%lld", &ava2[i]);
sort(ava1 + 1, ava1 + pr + 1, cmp);
sort(ava2 + 1, ava2 + nf + 1, cmp);
ava1[0] = unique(ava1 + 1, ava1 + pr + 1) - ava1 - 1;
ava2[0] = unique(ava2 + 1, ava2 + nf + 1) - ava2 - 1;
for(int i = 1; i <= ava1[0]; i++) ava[i] = ava1[i];
for(int i = 1; i <= ava2[0]; i++) ava[i + ava1[0]] = ava2[i];
sort(ava + 1, ava + ava1[0] + ava2[0] + 1, cmp);
for(ll i = 1; i <= ava1[0] + ava2[0]; i++)
if(ava[i] == ava[i - 1] && ava[i + 1] != ava[i])
ava[++ava[0]] = ava[i];
if(ava[0] == 0) {printf("0\n"); return 0;}
mat ans; ans.clear(); ans.c = ans.r = ava[ava[0]]; //建立矩阵
for(ll i = 1; i <= ava[0]; i++) ans.m[1][ava[i]] = 1;
for(ll i = 2; i <= ava[ava[0]]; i++) ans.m[i][i - 1] = 1;
ans = qpow(ans, n);//快速幂
printf("%lld\n", ans.m[1][1]); //自己手算一下，就发现只要输出左上角就可以了
return 1; //抄答案的是坏孩纸哦qwq
}
mat matMul(mat m1, mat m2){
mat ret;
ret.r = m1.r; ret.c = m2.c;
for(int i = 1; i <= ret.r; i++)
for(int j = 1; j <= ret.c; j++){
ll t = 0;
for(int k = 1; k <= m1.c; k++)
t = (t + (m1.m[i][k] * m2.m[k][j]) % MOD) % MOD;
ret.m[i][j] = t;
}
return ret;
}
void prt(mat m){
for(ll i = 1; i <= m.c; i++){
for(ll j = 1; j <= m.r; j++)
printf("%lld ", m.m[i][j]);
putchar('\n');
}
putchar('\n');
}
mat qpow(mat x, ll powers){
mat ret; ret.clear(); ret.r = x.r; ret.c = x.c;
for(ll i = 1; i <= ret.r; i++)
ret.m[i][i] = 1;
while(powers){
if(powers & 1) ret = matMul(ret, x);
x = matMul(x, x);
powers >>= 1;
}
return ret;
}
```
总复杂度$O(x^3 \log n)$，最慢的点不开$O2$是$764ms$。
[我的提交](https://www.luogu.org/recordnew/show/18780010)
谢谢阅读我的第二篇题解
有疑问或错误请在评论区指出哦qwq