物联网网站开发公司,.net最新网站开发,宁波网络营销推广开发中心,各大网站矩阵快速幂习题复习矩阵乘法及快速幂模板乘法模板快速幂模板T1#xff1a;Arc of Dream题目题解codeT2#xff1a;Recursive sequence题目题解codeT3#xff1a;233 Matrix题目题解codeT4#xff1a;Training little cats题目题解code做题的时候后悔没有保存过模板#xf…
矩阵快速幂习题复习矩阵乘法及快速幂模板乘法模板快速幂模板T1Arc of Dream题目题解codeT2Recursive sequence题目题解codeT3233 Matrix题目题解codeT4Training little cats题目题解code做题的时候后悔没有保存过模板还到处去找自己曾经写过的模板然并卵还是重新写了一遍其实如果知道原理就不用背模板了 每次复习的时候打完就觉得自己记住了然而
复习矩阵乘法及快速幂模板
具体怎么乘的移步百度百科
乘法模板
struct Matrix {int n, m;LL c[MAXN][MAXN];Matrix () {memset ( c, 0, sizeof ( c ) );}Matrix operator * ( const Matrix a ) const {Matrix res;res.n n;res.m a.m;for ( int i 1;i n;i )for ( int j 1;j a.m;j )for ( int k 1;k m;k )res.c[i][j] ( res.c[i][j] c[i][k] * a.c[k][j] % mod ) % mod; return res;}
};快速幂模板
Matrix qkpow ( Matrix a, LL b ) {Matrix res;res.n a.n;res.m a.m;for ( int i 1;i res.n;i )res.c[i][i] 1;while ( b ) {if ( b 1 )res res * a;a a * a;b 1;}return res;
}T1Arc of Dream
题目
梦想之弧是由以下函数定义的曲线 ∑i0n−1aibi\sum_{i0}^{n-1}a_ib_ii0∑n−1aibi 其中 a0A0a_0 A0a0A0 aiai−1∗AXAYa_i a_{i-1} * AX AYaiai−1∗AXAY b0B0b_0 B_0b0B0 bibi−1∗BXBYb_i b_{i-1} * BX BYbibi−1∗BXBY AoDN取1,000,000,007模的值是多少 输入项 有多个测试用例。处理到文件末尾。 每个测试用例包含以下7个非负整数 N A0 AX AY B0 BX BY N不大于101810^{18}1018所有其他整数不大于2×1092×10^92×109 输出量 对于每个测试用例以模1,000,000,007输出AoDN。 样本输入 1 1 2 3 4 5 6 2 1 2 3 4 5 6 3 1 2 3 4 5 6 样本输出 4 134 1902
题解
首先最后快速幂后肯定要有求和的答案所以要占一位接着把转移要用到的AX,AY...AX,AY...AX,AY...也甩进加速矩阵中然后发现转移后的ai,bia_i,b_iai,bi还要加上某一些常数所以我们还要给一位常数项我们可以把初始矩阵定义常数项为111在加速矩阵中再乘上常数 初始矩阵 [0(当前求和答案)a0∗b0a0b01(常数项)]\begin{bmatrix} 0(当前求和答案)a_0*b_0a_0b_01(常数项) \end{bmatrix} [0(当前求和答案)a0∗b0a0b01(常数项)] 考虑如何转移写出加速矩阵 [100001AX∗AY0000AXAX000BX0BX00AY∗BYAYBY1]\begin{bmatrix} 10000\\ 1AX*AY000\\ 0AXAX00\\ 0BX0BX0\\ 0AY*BYAYBY1\\ \end{bmatrix} ⎣⎢⎢⎢⎢⎡110000AX∗AYAXBXAY∗BY00AX0AY000BXBY00001⎦⎥⎥⎥⎥⎤ 这一题我仔细地推一遍后面就不仔细推了可能直接给加速矩阵和初始矩阵
code
#include cstdio
#include cstring
#define LL long long
#define mod 1000000007
#define MAXN 10
LL N, A0, Ax, Ay, B0, Bx, By;
struct Matrix {int n, m;LL c[MAXN][MAXN];Matrix () {memset ( c, 0, sizeof ( c ) );}Matrix operator * ( const Matrix a ) const {Matrix res;res.n n;res.m a.m;for ( int i 1;i n;i )for ( int j 1;j a.m;j )for ( int k 1;k m;k )res.c[i][j] ( res.c[i][j] c[i][k] * a.c[k][j] % mod ) % mod; return res;}void read () {for ( int i 1;i n;i )for ( int j 1;j m;j )scanf ( %lld, c[i][j] );}void print () {printf ( %lld\n, c[1][1] );}
}A;Matrix qkpow ( Matrix a, LL b ) {Matrix res;res.n a.n;res.m a.m;for ( int i 1;i res.n;i )res.c[i][i] 1;while ( b ) {if ( b 1 )res res * a;a a * a;b 1;}return res;
}int main() {while ( ~ scanf ( %lld, N ) ) {scanf ( %lld %lld %lld %lld %lld %lld, A0, Ax, Ay, B0, Bx, By );Matrix res;res.n res.m 5;res.c[1][1] res.c[2][1] res.c[5][5] 1;res.c[2][2] Ax * Bx % mod;res.c[3][2] Ax * By % mod;res.c[3][3] Ax % mod;res.c[4][2] Bx * Ay % mod;res.c[4][4] Bx % mod;res.c[5][2] Ay * By % mod;res.c[5][3] Ay % mod;res.c[5][4] By % mod;res qkpow ( res, N );A.n 1;A.m 5;A.c[1][1] 0;A.c[1][2] A0 * B0 % mod;A.c[1][3] A0 % mod;A.c[1][4] B0 % mod;A.c[1][5] 1;A A * res;A.print();}return 0;
}T2Recursive sequence
题目
Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i^4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.
Input The first line of input contains an integer t, the number of test cases. t test cases follow. Each case contains only one line with three numbers N, a and b where N,a,b231N,a,b 2^{31}N,a,b231 as described above. Output For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.
Sample Input 2 3 1 2 4 1 10 Sample Output 85 369
Hint In the first case, the third number is 852∗1十2十3485 2*1十2十3^4852∗1十2十34. In the second case, the third number is 932∗1十1∗10十3493 2*1十1*10十3^4932∗1十1∗10十34 and the fourth number is 3692∗10十93十44369 2 * 10 十 93 十 4^43692∗10十93十44. 一句话题意 给定a,ba,ba,b分别为第一项和第二项求第n项第i项等于2(i−2)(i−1)i42(i-2)(i-1)i^42(i−2)(i−1)i4
题解
2(i−1),(i−1)2(i-1),(i-1)2(i−1),(i−1)都很好转移但是i4i^4i4就有点难了我们可以这样处理 i4(i−11)4i^4(i-11)^4i4(i−11)4将i−1i-1i−1看作一个整体这样就运用二项式展开用到杨辉三角1,4,6,4,11,4,6,4,11,4,6,4,1但是这个时候又要知道i3,i2,i1,i01i^3,i^2,i^1,i^01i3,i2,i1,i01才能进行转移用同样的方式处理它们就可以进行转移了 初始矩阵 a,b,21,22,23,24,1a,b,2^1,2^2,2^3,2^4,1a,b,21,22,23,24,1 加速矩阵就不推了直接给 [0200000110000004123400601360040014001000100111111]\begin{bmatrix} 0200000\\ 1100000\\ 0412340\\ 0601360\\ 0400140\\ 0100010\\ 0111111\\ \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡0100000214641100100010021001003310100464110000001⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
code
#include cstdio
#include cstring
#define mod 2147493647
#define LL long long
#define maxn 10
int t;
LL n, a, b;struct Matrix {int n, m;LL c[maxn][maxn];Matrix () {memset ( c, 0, sizeof ( c ) );}Matrix operator * ( const Matrix a ) const {Matrix res;res.n n;res.m a.m;for ( int i 1;i n;i )for ( int j 1;j a.m;j )for ( int k 1;k m;k )res.c[i][j] ( res.c[i][j] c[i][k] * a.c[k][j] % mod ) % mod; return res;}void print() {printf ( %lld\n, c[1][2] );}
}A;Matrix qkpow ( Matrix a, LL b ) {Matrix ans;ans.n ans.m a.n;for ( int i 1;i a.n;i )ans.c[i][i] 1;while ( b ) {if ( b 1 )ans ans * a;a a * a;b 1;}return ans;
}int main() {scanf ( %d, t );while ( t -- ) {scanf ( %lld %lld %lld, n, a, b );if ( n 1 )printf ( %lld\n, a );if ( n 2 )printf ( %lld\n, b );Matrix tmp;tmp.n tmp.m 7;tmp.c[2][1] tmp.c[2][2] tmp.c[3][3] tmp.c[4][4] tmp.c[5][5] tmp.c[6][2] tmp.c[6][6] tmp.c[7][2] tmp.c[7][3] tmp.c[7][4] tmp.c[7][5] tmp.c[7][6] tmp.c[7][7] 1;tmp.c[1][2] tmp.c[3][4] 2;tmp.c[3][5] tmp.c[4][5] 3;tmp.c[3][2] tmp.c[3][6] tmp.c[5][6] tmp.c[5][2] 4;tmp.c[4][2] tmp.c[4][6] 6;tmp qkpow ( tmp, n - 2 );A.n 1;A.m 7;A.c[1][1] a;A.c[1][2] b;A.c[1][3] 2;A.c[1][4] 4;A.c[1][5] 8;A.c[1][6] 16;A.c[1][7] 1;A A * tmp;A.print();}return 0;
}T3233 Matrix
题目
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 … in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333… (it means a 0,1 233,a 0,2 2333,a 0,3 23333…) Besides, in 233 matrix, we got a i,j a i-1,j a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,…,a n,0, could you tell me a n,m in the 233 matrix? Input There are multiple test cases. Please process till EOF.
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10^9). The second line contains n integers, a 1,0,a 2,0,…,a n,0(0 ≤ a i,0 2 31). Output For each case, output a n,m mod 10000007. Sample Input 1 1 1 2 2 0 0 3 7 23 47 16 Sample Output 234 2799 72937
Hint
题解
看图↓ 我们可以考虑用对角线去处理因为nnn很小可以暴力算出第一根红线之前所有点的值 然后画出平移的一条线发现转移规律除了第一个点是直接由上一条线第一个点转移其余的点都是上一条线的对应点和上一个点的和我们以第一条对角线为初始矩阵那么进行mmm次转移即可用快速幂搞定
加速矩阵为 [110...00011...00001...00......000...10000...11000...01]\begin{bmatrix} 110...00\\ 011...00\\ 001...00\\ ......\\ 000...10\\ 000...11\\ 000...01 \end{bmatrix} ⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡100.000110.000011.000...................000.110000.011⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
code
#include cstdio
#include cstring
#define mod 10000007
#define LL long long
#define maxn 15
LL n, m;
LL a[maxn][maxn];struct Matrix {int n, m;LL c[maxn][maxn];Matrix () {memset ( c, 0, sizeof ( c ) );}Matrix operator * ( const Matrix a ) const {Matrix res;res.n n;res.m a.m;for ( int i 1;i n;i )for ( int j 1;j a.m;j )for ( int k 1;k m;k )res.c[i][j] ( res.c[i][j] c[i][k] * a.c[k][j] % mod ) % mod; return res;}void print() {printf ( %lld\n, c[1][m - 1] );}
}A;Matrix qkpow ( Matrix a, LL b ) {Matrix ans;ans.n ans.m a.n;for ( int i 1;i a.n;i )ans.c[i][i] 1;while ( b ) {if ( b 1 )ans ans * a;a a * a;b 1;}return ans;
}int main() {while ( ~ scanf ( %lld %lld, n, m ) ) {for ( int i 1;i n;i )scanf ( %lld, a[i][0] );a[0][1] 233;for ( int i 2;i n;i )a[0][i] ( a[0][i - 1] * 10 % mod 3 ) % mod;for ( int i 1;i n;i )for ( int j 1;j n - i;j )a[i][j] ( a[i - 1][j] a[i][j - 1] ) % mod;A.n 1;A.m n 2;for ( int i 1;i n 1;i )A.c[1][i] a[i - 1][n - i 1];A.c[1][n 2] 3;Matrix res;res.n res.m n 2;res.c[1][1] 10;res.c[n 2][1] res.c[n 2][n 2] 1;for ( int i 2;i n 1;i )res.c[i][i] res.c[i - 1][i] 1;res qkpow ( res, m );A A * res;A.print();}return 0;
}T4Training little cats
题目
Facer’s pet cat just gave birth to a brood of little cats. Having considered the health of those lovely cats, Facer decides to make the cats to do some exercises. Facer has well designed a set of moves for his cats. He is now asking you to supervise the cats to do his exercises. Facer’s great exercise for cats contains three different moves: g i : Let the ith cat take a peanut. e i : Let the ith cat eat all peanuts it have. s i j : Let the ith cat and jth cat exchange their peanuts. All the cats perform a sequence of these moves and must repeat it m times! Poor cats! Only Facer can come up with such embarrassing idea. You have to determine the final number of peanuts each cat have, and directly give them the exact quantity in order to save them.
Input The input file consists of multiple test cases, ending with three zeroes “0 0 0”. For each test case, three integers n, m and k are given firstly, where n is the number of cats and k is the length of the move sequence. The following k lines describe the sequence. (m≤1,000,000,000, n≤100, k≤100)
Output For each test case, output n numbers in a single line, representing the numbers of peanuts the cats have.
Sample Input 3 1 6 g 1 g 2 g 2 s 1 2 g 3 e 2 0 0 0 Sample Output 2 0 1
题解
分三种情况可以考虑多给加速矩阵提供一行常数项 ggg就直接111 eee就将该只小猫的那一列全部清零 sss就直接swapswapswap交换两列 最后直接快速幂即可比较简单
code
#include cstdio
#include cstring
#include iostream
using namespace std;
#define LL long long
#define maxn 105struct Matrix {int n, m;LL c[maxn][maxn];Matrix () {memset ( c, 0, sizeof ( c ) );}Matrix operator * ( const Matrix a ) {Matrix ans;ans.n n;ans.m a.m;for ( int i 1;i n;i )for ( int k 1;k m;k )if ( c[i][k] )for ( int j 1;j a.m;j )ans.c[i][j] c[i][k] * a.c[k][j];return ans;}void print() {for ( int i 1;i m;i )printf ( %lld , c[1][i] );printf ( \n );}
}A;Matrix qkpow ( Matrix a, LL b ) {Matrix ans;ans.n a.n;ans.m a.m;for ( int i 1;i ans.n;i )ans.c[i][i] 1;while ( b ) {if ( b 1 )ans ans * a;a a * a;b 1;}return ans;
}int main() {int n, m, k, cat, Cat;char opt;while ( ~ scanf ( %d %d %d, n, m, k ) ) {if ( ! n ! m ! k )return 0;memset ( A.c, 0, sizeof ( A.c ) );A.n 1;A.m n 1;A.c[1][n 1] 1;Matrix ans;ans.n n 1;ans.m n 1;for ( int i 1;i ans.n;i )ans.c[i][i] 1;for ( int i 1;i k;i ) {getchar();scanf ( %c %d, opt, cat );if ( opt g )ans.c[ans.m][cat] ;else if ( opt e ) {for ( int j 1;j ans.n;j )ans.c[j][cat] 0;} else {scanf ( %d, Cat );for ( int j 1;j ans.n;j )swap ( ans.c[j][cat], ans.c[j][Cat] );}}ans qkpow ( ans, m );A A * ans;A.print();}return 0;
}有任何问题欢迎提出byebye
