NYOJ-1273-宣传墙

2019-11-08 01:37:30

字体：大中小

来源：转载

供稿：网友

ACM模版

描述

题解

这个问题十分有趣，因为我做不出来！！！

去年河南 ACM 省赛的第二道题，当时耽搁了我好久好久时间依然无果，最后只好作罢，放了好久没有补，今天忽然想起来，看了看代码，发现并不能完全理解，但是知道这道题肯定是递推找规律的，然而我就是静不下心来慢慢发掘其规律。作为一个职业马后炮，需要说的是，这个题可以用 dp 解，也可以用矩阵快速幂解，但是两种方法都不外乎递推找规律，那么问题来了，这个递推是什么呢？

一开始，我看了矩阵快速幂的解法，矩阵快速幂部分可以理解，但是递推部分的判断我却无法顿悟，0和1究竟表示什么？这个问题惆怅了我一下午，晚上搞来了一份神犇的题解手稿照片，看了后，顿悟啊，点赞，杠杠的，在此，为表达对神犇虔诚的敬意，故将此题解照片分享给大家，虽然不知道神犇何许人也，但是还是十分感谢他这份牛逼哄哄的题解~~~渣渣在此献上膝盖——Orz

（1）这里写图片描述（2）（3）（4）（5）（6）（7）

大人真乃神人也~~~

最后，这个题用 dp 写需要用到状压 dp + 滚动数组，既费时又费钱，用矩阵快速幂搞会快很多很多，也更加经济实惠。

代码

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int MOD = 997;const int MAXN = 16;struct mat{ int A[MAXN][MAXN]; mat() { memset(A, 0, sizeof(A)); } mat Operator * (const mat &a) const { mat b; for (int i = 0; i < MAXN; i++) { for (int j = 0; j < MAXN; j++) { for (int k = 0; k < MAXN; k++) { b.A[i][j] += A[i][k] * a.A[k][j]; b.A[i][j] %= MOD; } } } return b; }};mat map;bool cmp(int i, int j) // 状态 j 对状态 i 是否可行 j 是 col 列的状态 i 是 col - 1 列的状态{ for (int row = 0; row < 4; row++) { if ((i >> row) & 1) { if ((j >> row) & 1) {// if (row == 3) // 这个特判有没有都行，因为 i >> 4 肯定为 0// { // 这样不过是思维更严谨些// return false;// } if ((i >> (row + 1)) & 1) { i -= (1 << (row + 1)); // 等价于 i ^= 1 << (rank + 1)，前边的写法不太直观 } else { return false; } } else { continue; } } else { if ((j >> row) & 1) { continue; } else { return false; } } } return true;}// 构造单元矩阵void unit(){ for (int i = 0; i < MAXN; i++) { for (int j = 0; j < MAXN; j++) { map.A[i][j] = cmp(i, j); } }}int slove(int n){ mat a; mat b = map; for (int i = 0; i < MAXN; i++) { a.A[i][i] = 1; } while (n) { if (n & 1) { a = a * b; } b = b * b; n >>= 1; } return a.A[MAXN - 1][MAXN - 1];}int main (){ int T; scanf("%d", &T); unit(); while (T--) { int N, M, K; scanf("%d%d%d", &N, &M, &K); PRintf("%d %d/n", slove(M - 1), slove(N - M - K + 1)); } return 0;}

上一篇：LINUX CENTOS 7 X86_64中开始菜单的编辑安装软件alacarte即可

下一篇：Unity初学入门1 学习笔记（已初步了解Unity界面与C#脚本语言）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注