题意
题目链接
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 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606131.html