容易被忽略的东西
线段树优化DP
概率/期望DP
　　有一些概率/期望DP可以快速地推出这样的式子：
\begin{align}
f_i&=a+bf_i\\
(1-b)f_i&=a\\
f_i&=\frac{a}{1-b}
\end{align}
　　BZOJ4872
　　XSY2472
　　有一些问题求得是只包含/不包含一个点的情况，只需要考虑当前\([l,r]\)对\([l,mid]\)和\([mid+1,r]\)的影响。
　　下面来讲一道例题
　　\(A(x)\)为\(n-1\)次多项式，\(B_i(x)\)为一次多项式，\(\forall i\)求\(A(x)\mod B_i(x)\)
　　直接做是\(O(n^2)\)的。
　　因为\((A(x)\mod C(x))\mod B_i(x)=A(x)\mod B_i(x)\)（\(C(x)\mod B_i(x)=0\)）
　　设当前已经求出了
D_{l,r}=A(x)\mod(\prod_{i=l}^rB_i(x))
\begin{align}
D_{l,mid}&=D_{l,r}\mod(\prod_{i=l}^{mid}B_i(x))\\
D_{mid+1,r}&=D_{l,r}\mod(\prod_{i=mid+1}^{r}B_i(x))
\end{align}
　　所以我们可以递归下去做，直到求出所有的\(D_{i,i}\)
　　时间复杂度：
T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)
　　多点求值
　　XSY2469
欧拉phi函数
　　就是\(\phi\)函数
　　谁都知道这个东西是个积性函数。
\varphi(ab)=\varphi(a)\varphi(b)~~~((a,b)=1)
　　那如果\((a,b)\neq 1\)呢？
　　设\(d=(a,b)\)
\begin{align}
\varphi(a)&=a(1-\frac{1}{p1_1})(1-\frac{1}{p1_2})\cdots(1-\frac{1}{p1_{n1}})\\
\varphi(b)&=b(1-\frac{1}{p2_1})(1-\frac{1}{p2_2})\cdots(1-\frac{1}{p2_{n2}})\\
\varphi(ab)&=ab(1-\frac{1}{p3_1})(1-\frac{1}{p3_2})\cdots(1-\frac{1}{p3_{n3}})\\
\varphi(d)&=d(1-\frac{1}{p4_1})(1-\frac{1}{p4_2})\cdots(1-\frac{1}{p4_{n4}})
\end{align}
　　可以发现，对于后面那部分
\begin{align}
(1-\frac{1}{p1_1})(1-\frac{1}{p1_2})\cdots(1-\frac{1}{p1_{n1}})\times
(1-\frac{1}{p2_1})(1-\frac{1}{p2_2})\cdots(1-\frac{1}{p2_{n2}})\\
=(1-\frac{1}{p3_1})(1-\frac{1}{p3_2})\cdots(1-\frac{1}{p3_{n3}})\times
(1-\frac{1}{p4_1})(1-\frac{1}{p4_2})\cdots(1-\frac{1}{p4_{n4}})
\end{align}
　　如果\(p\)只在\(a\)或\(b\)中出现过，那么只会在\(ab\)中出现。如果同时在\(a\)和\(b\)中出现过，那么会同时在\(ab\)和\(d\)中出现。
　　所以有
\varphi(ab)=\frac{\varphi(a)\varphi(b)d}{\varphi(d)}~~~(d=(a,b))
　　有时候我们做某个操作很不好做，我们可以先把所有操作做完后在一个个回复。
　　例如：给以一个图，有两种操作：1.删边；2.询问连通性。
　　我们可以先把需要删的边删掉，再一个个加回来，用并查集维护连通性。
　　有时候问你\(\forall A\)，满足要求的\(B\)的和。
　　我们可以枚举所有的\(B\)，计算每个\(B\)对每个\(A\)的贡献。
　　AGC005F
一类全序问题
　　有\(n\)个物品，你要依次选择这些物品，每个物品有三个属性\(a_i,b_i,c_i\)，当你选择一个物品后，设当前选择的物品的\(c\)属性的和为\(s\)，那么选择这个物品的收益是\(a_i+b_is\)，问你最大收益是多少。
　　假设我们已经钦定了一个顺序。考虑两个相邻的物品（不妨设为前两个），什么时候当前顺序比交换后更优：
\begin{align}
a_1+a_2+b_2c_1&&a_2+a_1+b_1c_2\\
b_2c_1&&b_1c_2\\
\frac{c_1}{b_1}&&\frac{c_2}{b_2}
\end{align}
　　这样我们就得到了一个全序关系。
　　那么能不能扩展到任意两个物品的情况呢？
\begin{align}
a_i+b_ix+a_j+b_j(x+y+c_i)&&a_j+b_jx+a_i+b_i(x+y+c_j)\\
b_jy+b_jc_i&&b_iy+b_ic_j\\
\frac{c_i+y}{b_i}&&\frac{c_j+y}{b_j}\\
\end{align}
　　好像并不太行。我们需要换一种思路。
　　假设我们找到了一种最优解，但并不满足以上的性质，那么一定可以交换相邻两个物品使得答案最优。所以直接排序贪心可以得到最优解。
　　如果题目还有其他限制，你也可以在得到这个顺序后DP或者干其他事情。
　　总所周知，莫队的时间复杂度和块大小有关。
　　如果块大小为\(t\)，时间复杂度为\(O(\frac{n^2}{t}+mt)\)
　　如果块大小为\(\sqrt n\)，时间复杂度为\(O((n+m)\sqrt n)\)
　　如果块大小为\(\frac{n}{\sqrt{m}}\)，时间复杂度为\(O(n\sqrt m+m\log m)\)
　　所以有时候可以通过调整块大小来加速。俗称调参。
一类单点修改区间求和的问题
　　有时候我们要修改一个点，求区间和。
|算法|修改|求和|
|:----:|:----:|:----:|
|树状数组/线段树|\(O(log n)\)|\(O(logn)\)|
|分块1|\(O(1)\)|\(O(\sqrt n)\)|
|分块2|\(O(\sqrt n)\)|\(O(1)\)|
　　树状数组/线段树的做法很经典，这里就不讲了。
　　分块1：每次修改把对应的位置和对应的块的和\(+1\)
　　分块2：每次修改把对应的位置和对应的块的和\(+1\)，然后求出块内前缀和、块内后缀和、块的前缀和。
　　有的人就要问了，分块做法那么慢，有什么用呢？
　　用处大着呢！当修改次数与询问次数不平衡的时候，我们可以做到比树状数组更优。
　　博主曾经用莫队+分块1水过了一道\(n=m={10}^6\)的题。跑的比zjt神犇的线段树合并还快。
和排列有关的问题
　　很多问题让你求对于每一个排列\(A\)，如果\(\cdots\)，那么\(\cdots\)。
　　我们可以考虑从小到大插入这\(n\)个数，插入第\(i\)个数时考虑这个数的贡献。
用trie实现全部数\(+1\)，查询全部数的异或和
　　我们从低位到高位建一棵trie树。
　　从根开始，交换左右子树，然后对\(0\)的那棵子树执行同样的操作（进位）。
莫比乌斯反演的多组询问
\begin{align}
ans&=\sum_{i=1}^lc^{\gcd(i,b)}\\
&=\sum_{d|s}c^d\sum_{i=1}^l[\gcd(i,s)=d]\\
&=\sum_{d|s}c^d\sum_{i=1}^{\frac{l}{d}}[\gcd(i,\frac{s}{d})=1]\\
&=\sum_{d|s}c^d\sum_{i|\frac{s}{d}}\mu(i)\lfloor\frac{l}{id}\rfloor\\
\end{align}
　　看起来没办法化简了
　　这时候要枚举\(j=id\)
\begin{align}
ans&=\sum_{j|s}\lfloor\frac{l}{j}\rfloor\sum_{i|j}\mu(i)c^\frac{j}{i}\\
\end{align}
　　设\(f(x)=\sum_{i|x}\mu(i)c^\frac{x}{i}\)
　　这样\(f(x)\)就可以预处理出来了。
\begin{align}
ans&=\sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j))\\
&=\sum_{i=1}^{\min(n,m)}f(i)\sum_{i|j}\mu(\frac{j}{i})\lfloor\frac{n}{j}\rfloor\lfloor\frac{m}{j}\rfloor\\
&=\sum_{i=1}^{\min(n,m)}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor\sum_{j|i}f(j)\mu(\frac{i}{j})
\end{align}
　　这样可以预处理后面的\(g(n)=\sum_{i|n}\mu(\frac{n}{i})f(i)\)
　　每次枚举前面询问。
　　时间复杂度：\(O(n+T\sqrt{n})\)　　
莫比乌斯反演
　　有很多题推着推着就推到\(\varphi\)上面去了。
　　说明可以用一条式子：\(\sum_{d|n}\varphi(d)=n\)
　　分治FFT一般有两个用途。
求很多个多项式的乘积（普通分治）
　　设有\(n\)个多项式，次数之和是\(m\)，那么时间复杂度就是\(O(m\log m\log n)\)。一共有\(\log n\)层，每层是\(O(m\log m)\)的。
求一类数列（CDQ分治）
　　数列\(f_n=\sum_{i=0}^{n-1}f_ig_{n-i}\)。对于一个分治区间\([l,r]\)，先求出\([l,mid]\)的答案，再计算这部分对右边\([mid+1,r]\)的贡献。
　　时间复杂度：\(O(n\log^2 n)\)
矩阵快速幂+FFT
　　DP转移如下：
f_{i+1,j',k+v}+=f_{i,j,k}
　　\(i\leq n,j\leq l,k\leq m\)
　　其中\(v\)只与\(j\)有关，最后求\(k=s\)或\(k\mod m=s\)的值的和。
　　暴力搞的时间复杂度是\(O(l^3m^3\log n)\)的。
　　我们可以把这个东西看成一个多项式。
g_{i,j}=\sum_{k\geq 0}f_{i,j,k}x^k
　　转移就可以看成乘以一个多项式（单项式）。
　　如果求的是\(k\mod m=s\)的值的和，就可以看成循环卷积。
　　可以先求值，把每个点值拿去跑一遍矩阵快速幂，再插值回来。
　　时间复杂度：\(O(ml^3\log n)+\)点值插值的时间复杂度\(O(m^2)/O(m\log m)\)
多组询问的矩阵快速幂优化DP
　　设矩阵大小为\(m\)，次数是\(n\)，询问组数是\(t\)，朴素的实现是\(O(tm^3\log n)\)的。
　　可以先把转移矩阵的\(i\)次幂求出来。
　　每次询问只需要拿一个\(1\times m\)的矩阵去乘转移矩阵就行了。每次乘法是\(O(m^2)\)的。
　　时间复杂度：\(O(m^3+tm^2\log n)\)
\sum_{i=j}^{n-k}\binom{i}{j}\binom{n-i}{k}=\binom{n+1}{j+k+1}
　　可以用插板法理解。
树上的连通块
　　树上连通块个数\(=\)点数\(-\)边数。
　　点数/边数中一般有一个是固定的。
轻重链剖分&长链剖分
轻重链剖分
　　每个重链顶端的子树大小总和是 \(O(n\log n)\) 的。
　　每个点到根经过的轻边个数是 \(O(\log n)\) 的。
　　适用于维护与树的大小有关的信息。
　　每个长链顶端的子树深度总和是 \(O(n)\) 的。
　　适用于维护与树的深度有关的信息。
高维前缀和 & 莫比乌斯反演
　　复杂度为 \(O(\sum_{i}\frac{n}{p_i})=O(n\log log n)\)
g(n)=\sum_{d\mid n}f(d)
for(int i=1;i&=i++)
for(int j=1;j*pri[i]&=n;j++)
f[j*pri[i]]+=f[j];
g(n)=\sum_{n\mid d}f(d)
for(int i=1;i&=i++)
for(int j=n/pri[i];j&=0;j--)
f[j]+=f[j*pri[i]];
g(n)=\sum_{d\mid n}f(d)\mu(\frac{n}{d})
for(int i=1;i&=i++)
for(int j=n/pri[i];j&=0;j--)
f[j*pri[i]]-=f[j];
g(n)=\sum_{n\mid d}f(d)\mu(\frac{d}{n})
for(int i=1;i&=i++)
for(int j=1;j*pri[i]&=n;j++)
f[j]-=f[j*pri[i]];
　　如果要的是最大收益，那么可以先强制选所有正的边，然后把不选一条边看成割掉这条边，答案为正的边权和 \(-\) 最小割。
　　可以先对于每条边钦定一个方向，然后如果一条边有流量就表示这条边改了方向。对于一个点 \(i\)，要根据出度入度的关系向源/汇连边。
　　把每一行看做一个点，把每一列看做一个点，选一个格子就在对应的行列之间连边。
　　这是一个分层图，用 dinic 跑会比较快。
　　每个物品对应一条链，割一条边代表这个物品对应的数/放在什么位置。
　　\(i\) 对应的链割了点 \(x\) 后面的边时 \(j\) 对应的链必须割点 \(y\) 后面的边
　　解决方法为连边 \((x,y,\infty)\)。
　　有时候限制是 \(i\) 割了点 \(x\) 后面的边时 \(j\) 必须割点 \(y\) 前面的边
　　那么就要把一边的链反过来。
　　常见的方法有：
　　　横着的链不变，竖着的链反过来。
　　　黑白染色，白色的点对应的链不变，黑色的点对应的链反过来。
　　要注意前面的点属于 T 集且后面的点属于 S 集的情况。
　　要从后面的点往前面的点连容量为 \(\infty\) 的边。
　　二叉树的点分树中每个节点只有至多 \(3\) 个儿子。这样可以直接可持久化这棵点分树，可以减少一个 \(\log\)（把点分树当成三叉数可持久化，深度是 \(\log\) 的）。
最小树形图
　　用可合并堆维护每个点的最小入边，可以做到 \(O(n+m)\log m\)
一类 每次在剩下的物品中选一种拿走一个，求拿走的最后一个物品是第一种物品的概率 的问题
　　考虑容斥，枚举哪些物品是在第一种物品拿完之后拿走的（剩下的随意）。
　　那么剩下的物品就可以忽略了，只需要求出第一种物品是第一个拿完的概率。
这道题，可以DP
　　　考虑拿走第一种物品时每种物品拿了几个，就可以DP了：
　　　设 \(f_{i,j,k}\) 表示考虑完了前 \(i\) 种物品，有 \(j\) 种要在第一种取完之后才取完，已经取了 \(k\) 个物品。
　　　最终长度为 \(l\) ，取了 \(j\) 种的序列的序列的贡献是 方案数 \(\times {(-1)}^j\times {(\frac{1}{j+1})}^l\)
这道题，第一种物品是第一个取完的概率是 \(\frac{w_1}{\sum w_i}\)。可以用分治 NTT 计算方案数。
阅读(...) 评论()“蓝桥杯”练习系统
登录后才能查看试题。
主办单位：工业和信息化部人才交流中心
地址：北京市海淀区万寿路27号院工信部机关18#信箱 邮编: 100846
电话： 传真：010- 京ICP备号 京公网安备 52号
关注订阅号，资讯先了解！
关注服务号，轻松查成绩！
请用微信扫描之后即可进入蓝桥杯提供功能数据规模和约定
#include &stdio.h&
#define BIG
int iskonw[4][3]={
int jieguo[99999][3];//动态规划
/*int fun(int n,int num){
//粗糙的动态规划，题目系统里只得了40分
int temp=0;
if(n-3&=1){
if(jieguo[n][num]!=0) return jieguo[n][num]%BIG;
if(num==1)
temp=fun(n-1,2)+2*fun(n-3,1)+5;
else if(num==2)
temp=fun(n-1,1)+3*fun(n-3,1)+2*fun(n-3,2)+3;
jieguo[n][num]=
return iskonw[n][num];
return temp%BIG;
int fun2(long n,int num,int tag){
long temp=0;
long F1[4],F2[4];
F1[1]=6; F2[1]=5;
F1[2]=1; F2[2]=4;
F1[3]=2; F2[3]=3;
for(i=4;i&=n;i++){
F1[0]=(F2[1]+2*F1[3]+5)%BIG;
F2[0]=(F1[1]+3*F1[3]+2*F2[3]+3)%BIG;
for(j=3;j&=1;j--){
F1[j]=F1[j-1];
F2[j]=F2[j-1];
return iskonw[n][num];
if(tag==1) return F1[0];
return F2[0];
int main()
scanf("%d",&n);
printf("%d\n",fun2(n,1,1));
printf("%d\n",fun2(n,2,2));
#include&iostream&
#include&cstring&
#define MOD
long long**
void mul_mat(Mat a, Mat b, Mat &c, int R_number_a, int C_number_a, int C_number_b)
Mat C = new long long*[R_number_a];
for (int i = 0;i&R_number_a;i++)
C[i] = new long long[C_number_b];
for (int j = 0;j&C_number_b;j++)
C[i][j] = 0
for ( i = 0;i&R_number_a;i++)
for ( k = 0;k & C_number_a;k++)
for ( j = 0;j&C_number_b;j++)
C[i][j] += a[i][k] * b[k][j]%MOD;
Mat pow_mat(Mat region, int R_number, int C_number, long long n)
Mat ans = new long long*[R_number];
Mat t = new long long*[R_number];
for (int i = 0;i&R_i++)
ans[i] = new long long[C_number];
for (int j = 0;j&C_j++)
ans[i][j] = (long long)(i == j);
for (int i = 0;i&R_i++)
t[i] = new long long[C_number];
for (int j = 0;j&C_j++)
t[i][j] = region[i][j];
if (n & 1)
mul_mat(ans, t, ans, R_number, C_number, C_number);
mul_mat(t, t, t, R_number, C_number, C_number);
n = n && 1;
int main()
Mat region = new long long*[7],
long long n, a[7] = {5ll,6ll,4ll,1ll,3ll,2ll,1ll};
region[0] = new long long[7];
region[1] = new long long[7];
for (int i = 0;i & 7;i++)
region[i] = new long long[7],memset(region[i],0,sizeof(long long)*7);
region[0][1]= region[1][0]= region[2][0]= region[3][1]= region[4][2]= region[5][3]= region[6][6]=1
region[0][4] = 2
region[0][5] = 3
region[0][6] = 3
region[1][5] = 2
region[1][6] = 5
if (n & 4) {
switch (n) {
case 1:cout && 2 && endl && 3 &&
case 2:cout && 1 && endl && 4&&
case 3:cout && 6 && endl && 5 &&
ans = pow_mat(region, 7, 7, n - 3);
long long fn1 = 0ll, fn2 = 0
for (int i = 0;i & 7;i++)
fn1 += ans[1][i] * a[i], fn2+= ans[0][i] * a[i];
cout && fn1%MOD && endl && fn2%MOD &&
五种典型的递推关系——一步一步算法篇
算法提高 递推求值 (矩阵快速幂)
算法提高 递推求值
【矩阵快速幂】
蓝桥杯算法提高——递推求值（矩阵快速幂）
算法提高 递推求值
没有更多推荐了，　　已知递推公式：
　　F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,
　　F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.
　　初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。
　　输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以的余数。
　　输入第一行包含一个整数n。
　　输出两行，第一行为F(n, 1)除以的余数，第二行为F(n, 2)除以的余数。
数据规模和约定
　　1&=n&=10^18。
这个题数据量很大，如果直接递推的话，一定会超时，所以采用矩阵快速幂的方法，将时间复杂度由o(n)降低为o(logn),不懂矩阵快速幂的可自行百度。#include&iostream&
#include&cstring&
#define MOD
long long**
void mul_mat(Mat a, Mat b, Mat &c, int R_number_a, int C_number_a, int C_number_b)
Mat C = new long long*[R_number_a];
for (int i = 0;i&R_number_a;i++)
C[i] = new long long[C_number_b];
for (int j = 0;j&C_number_b;j++)
C[i][j] = 0
for ( i = 0;i&R_number_a;i++)
for ( k = 0;k & C_number_a;k++)
for ( j = 0;j&C_number_b;j++)
C[i][j] += a[i][k] * b[k][j]%MOD;
Mat pow_mat(Mat region, int R_number, int C_number, long long n)
Mat ans = new long long*[R_number];
Mat t = new long long*[R_number];
for (int i = 0;i&R_i++)
ans[i] = new long long[C_number];
for (int j = 0;j&C_j++)
ans[i][j] = (long long)(i == j);
for (int i = 0;i&R_i++)
t[i] = new long long[C_number];
for (int j = 0;j&C_j++)
t[i][j] = region[i][j];
if (n & 1)
mul_mat(ans, t, ans, R_number, C_number, C_number);
mul_mat(t, t, t, R_number, C_number, C_number);
n = n && 1;
int main()
Mat region = new long long*[7],
long long n, a[7] = {5ll,6ll,4ll,1ll,3ll,2ll,1ll};
region[0] = new long long[7];
region[1] = new long long[7];
for (int i = 0;i & 7;i++)
region[i] = new long long[7],memset(region[i],0,sizeof(long long)*7);
region[0][1]= region[1][0]= region[2][0]= region[3][1]= region[4][2]= region[5][3]= region[6][6]=1
region[0][4] = 2
region[0][5] = 3
region[0][6] = 3
region[1][5] = 2
region[1][6] = 5
if (n & 4) {
switch (n) {
case 1:cout && 2 && endl && 3 &&
case 2:cout && 1 && endl && 4&&
case 3:cout && 6 && endl && 5 &&
ans = pow_mat(region, 7, 7, n - 3);
long long fn1 = 0ll, fn2 = 0
for (int i = 0;i & 7;i++)
fn1 += ans[1][i] * a[i], fn2+= ans[0][i] * a[i];
cout && fn1%MOD && endl && fn2%MOD &&
蓝桥杯-递推求值
nyoj--301--递推求值（经典矩阵运算）
打印大X 2015年蓝桥杯省赛
【蓝桥杯】扑克牌移动
2017蓝桥杯--承压计算
没有更多推荐了，蓝桥杯算法提高 递推求值
【矩阵快速幂】 - asuml - 博客园
& 算法提高 递推求值 &
　　已知递推公式： 　　F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,　　F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.　　初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。 　　输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以的余数。
　　输入第一行包含一个整数n。
　　输出两行，第一行为F(n, 1)除以的余数，第二行为F(n, 2)除以的余数。
数据规模和约定
　　1&=n&=10^18
第一次做矩阵快速幂的题目开始做的一塌糊涂，看到了这篇文章的启发http://www.cnblogs.com/frog112111/archive//3087648.html解释的很明白。
题目分析：
构造一个1×8的矩阵[f(n-1,1),f(n-1,2),f(n-2,1),f(n-2,2),f(n-3,1),f(n-3,2),5,3]
，根据递推关系，可以通过乘以一个8×8的矩阵A，得到矩阵[f(n,1),f(n,2),f(n-1,1),f(n-1,2),f(n-2,1),f(n-2,2),5,3]，算出矩阵A，即：
0,1,1,0,0,0,0,0,
1,0,0,1,0,0,0,0,
0,0,0,0,1,0,0,0,
0,0,0,0,0,1,0,0,
2,3,0,0,0,0,0,0,
0,2,0,0,0,0,0,0,
1,0,0,0,0,0,1,0,
0,1,0,0,0,0,0,1
之后再利用矩阵快速幂的方法得到结果。
#include &iostream&
#include &cstring&
using namespace
struct matrix
long long a[<span style="color: #][<span style="color: #];
matrix multiply(matrix x,matrix y,int m,int n,int s)//m*s
memset(temp.a,<span style="color: #,sizeof(temp.a));
for(int i=<span style="color: #;i&m;i++)
for(int j=<span style="color: #;j&n;j++)
for(int k=<span style="color: #;k&s;k++)
temp.a[i][j]=(temp.a[i][j]+(x.a[i][k]*y.a[k][j])%<span style="color: #999999)%<span style="color: #999999;
int main()
matrix temp={
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,
<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #
long long f[<span style="color: #]={<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #,<span style="color: #},sum1,sum2,n;
memset(res.a,<span style="color: #,sizeof(res.a));
for(int i=<span style="color: #;i&<span style="color: #;i++)
res.a[i][i]=<span style="color: #;
if(n==<span style="color: #)
cout&&"<span style="color: #"&&endl&&"<span style="color: #"&&
if(n==<span style="color: #)
cout&&"<span style="color: #"&&endl&&"<span style="color: #"&&
if(n==<span style="color: #)
cout&&"<span style="color: #"&&endl&&"<span style="color: #"&&
if(n&=<span style="color: #)
n=n-<span style="color: #;
while(n)//矩阵快速幂
if(n&<span style="color: #)
res=multiply(res,temp,<span style="color: #,<span style="color: #,<span style="color: #);
n&&=<span style="color: #;
temp=multiply(temp,temp,<span style="color: #,<span style="color: #,<span style="color: #);
sum1=sum2=<span style="color: #;
for(int i=<span style="color: #;i&<span style="color: #;i++)
sum1=(sum1+(f[i]*res.a[i][<span style="color: #])%<span style="color: #999999)%<span style="color: #999999;
sum2=(sum2+(f[i]*res.a[i][<span style="color: #])%<span style="color: #999999)%<span style="color: #999999;
cout&&sum1&&endl&&sum2&&
return <span style="color: #;}