c/c++语言开发共享BZOJ2476: 战场的数目(矩阵快速幂)

题意 “题目链接” Sol 神仙题Orzzz 考虑两边是否有$1$ 设$f[i]$表示周长为$2i$的方案数 第一种情况:左侧或右侧有一个1,那么把这个1删去,对应的方案数为$f[i 1]$ 第二种情况:左侧和右侧都有一个1,把这两个1删去,对应的方案数为$f[i 2]$ 第三种情况:左侧右侧都没有 …


题意

题目链接

sol

神仙题orzzz

考虑两边是否有(1)

(f[i])表示周长为(2i)的方案数

第一种情况:左侧或右侧有一个1,那么把这个1删去,对应的方案数为(f[i – 1])

第二种情况:左侧和右侧都有一个1,把这两个1删去,对应的方案数为(f[i – 2])

第三种情况:左侧右侧都没有1,把最下面一层删去,对应的方案为(f[i – 1])

综上,递推式为(f[i] = 3f[i – 1] – f[i – 2])

最后再减去矩形的方案为(n / 2 – 1)

矩阵快速幂优化一下

#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10, mod = 987654321; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n; int add(int x, int y) {     if(x + y < 0) return x + y + mod;     return x + y >= mod ? x + y - mod : x + y; } int mul(int x, int y) {     return 1ll * x * y % mod; } struct ma {     int m[3][3];     ma() {         memset(m, 0, sizeof(m));     }     ma operator * (const ma &rhs) const {         ma ans;         for(int k = 1; k <= 2; k++)             for(int i = 1; i <= 2; i++)                 for(int j = 1; j <= 2; j++)                     ans.m[i][j] = add(ans.m[i][j], mul(m[i][k], rhs.m[k][j]));         return ans;     } }; ma matrixpow(ma a, int p) {     ma base;     for(int i = 1; i <= 2; i++) base.m[i][i] = 1;     if(p < 0) return base;     while(p) {         if(p & 1) base = base * a;         a = a * a; p >>= 1;     }     return base; } int main() {     while(scanf("%d", &n) && (n)) {         if((n & 1) || (n < 8)) {puts("0"); continue;}         if(n == 8) {printf("2n"); continue;}         n >>= 1;         ma a;         a.m[1][1] = 3; a.m[1][2] =  - 1;         a.m[2][1] = 1; a.m[2][2] = 0;         a = matrixpow(a, n - 5);         printf("%dn", add(add(mul(13, a.m[1][1]), mul(5, a.m[1][2])), -(n - 1)));     }     return 0; } /* 7 8 9 10 0 */
www.ctvol.com true Article c/c++语言开发共享BZOJ2476: 战场的数目(矩阵快速幂)

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/c-cdevelopment/606131.html

(0)
上一篇 2021年5月13日 下午6:33
下一篇 2021年5月13日 下午6:36

精彩推荐