如何做翻唱网站,深圳建设合同备案 网站,中国电影家协会成员,滨海新区网站建设地斗主
思路
看到这nnn非常大#xff0c;感觉一定是个结论公式题#xff0c;但是感觉又不像是排列组合#xff0c;于是可以考虑矩阵快速幂了#xff0c;所以关键就是得得到递推公式了。
我们将棋盘分成两部分n−num,numn - num, numn−num,num我们假定显然对num1,2,3,4,…地斗主
思路
看到这nnn非常大感觉一定是个结论公式题但是感觉又不像是排列组合于是可以考虑矩阵快速幂了所以关键就是得得到递推公式了。
我们将棋盘分成两部分n−num,numn - num, numn−num,num我们假定显然对num1,2,3,4,5num 1, 2, 3, 4, 5num1,2,3,4,5分别有1,4,2,3,2,31, 4, 2, 3, 2, 31,4,2,3,2,3种分法对应到原来一整块的部分上也就是ansnansn−14ansn−22ansn−33ansn−4……ans_n ans_{n - 1} 4ans_{n - 2} 2 ans_{n - 3} 3 ans_{n - 4}……ansnansn−14ansn−22ansn−33ansn−4……,并且后面的变化是由2,3,2,32, 3, 2, 32,3,2,3不断循环下去的所以我们只要将ansn−ansn−1ans_n - ans_{n - 1}ansn−ansn−1即可得到递推式ansnansn−15ansn−2ansn−3−ansn−4ans_n ans_{n - 1} 5ans_{n - 2} ans_{n - 3} - ans_{n - 4}ansnansn−15ansn−2ansn−3−ansn−4
接下来就是这么一个简单的矩阵乘法了 [a4a3a2a1][1100501000010000]\left [ \begin{matrix} a_4 a_3 a_2 a_1 \end{matrix} \right] \left [ \begin{matrix} 1 1 0 0\\5 0 1 0\\0001\\ 0000\end{matrix}\right] [a4a3a2a1]⎣⎢⎢⎡1500100001000010⎦⎥⎥⎤
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \n
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll f 1, x 0;char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return f * x;
}int mod, n;struct matrix {ll a[4][4];matrix operator * (matrix t) {matrix temp;for(int i 0; i 4; i) {for(int j 0; j 4; j) {temp.a[i][j] 0;for(int k 0; k 4; k) {temp.a[i][j] (temp.a[i][j] a[i][k] * t.a[k][j]) % mod;}}}return temp;}
};int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);int T read();while(T--) {n read(), mod read();if(n 4) {if(n 1) printf(%d\n, 1);else if(n 2) printf(%d\n, 5);else if(n 3) printf(%d\n, 11);else printf(%d\n, 36);continue;}matrix ans {36, 11, 5, 1};matrix a {1, 1, 0, 0,5, 0, 1, 0,1, 0, 0, 1,-1, 0, 0, 0};n - 4;while(n) {if(n 1) ans ans * a;a a * a;n 1;}printf(%lld\n, (ans.a[0][0] % mod mod) % mod);}return 0;
}
