【bzoj2476】战场的数目 矩阵乘法优化dp
2024-08-29 11:21:44
题目描述
(战场定义为对于最高的一列向两边都严格不增的“用积木搭成”的图形)
输入
输入文件最多包含25组测试数据,每个数据仅包含一行,有一个整数p(1<=p<=109),表示战场的图形周长。p=0表示输入结束,你的程序不应当处理这一行。
输出
对于每组数据,输出仅一行,即满足条件的战场总数除以987654321的余数。
样例输入
7
8
9
10
0
样例输出
0
2
0
9
题解
矩乘优化dp的一道神题。
显然答案=总数-矩形个数。
设$f[i]$表示周长为$2i$的方案数。
那么如果左右都没有高度为1的,那么可以删掉最下边一行,为$f[i-1]$。
如果左边或右边有高度为1的,那么可以删掉这一个,为$f[i-1](*2)$。
而如果左右都有高度为1的,那么可以删掉这两个,为$f[i-2]$,这种情况会重复计算,应该减去。
最后的状态转移方程即为$f[i]=3f[i-1]-f[i-2]$,使用矩乘加速转移即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 987654321;
struct data
{
ll v[2][2];
data() {memset(v , 0 , sizeof(v));}
data(int x) {memset(v , 0 , sizeof(v)) , v[0][0] = v[1][1] = 1;}
data operator*(const data a)const
{
data ans;
int i , j , k;
for(i = 0 ; i < 2 ; i ++ )
for(j = 0 ; j < 2 ; j ++ )
for(k = 0 ; k < 2 ; k ++ )
ans.v[i][j] = (ans.v[i][j] + v[i][k] * a.v[k][j]) % mod;
return ans;
}
data operator^(const ll a)const
{
data x = *this , ans(1);
ll y = a;
while(y)
{
if(y & 1) ans = ans * x;
x = x * x , y >>= 1;
}
return ans;
}
}A , B;
int main()
{
A.v[0][0] = A.v[0][1] = 1;
B.v[0][1] = mod - 1 , B.v[1][0] = 1 , B.v[1][1] = 3;
ll p;
while(~scanf("%lld" , &p) && p)
{
if(p & 1 || p == 2) printf("0\n");
else printf("%lld\n" , ((A * (B ^ (p / 2 - 1))).v[0][0] - p / 2 + 1 + mod) % mod);
}
return 0;
}
最新文章
- 浅谈Excel开发:七 Excel 自定义任务窗体
- Yii里文件上传的操作方法(图片修改,在详情上展示,批量上传待续...)
- 我为什么反对推荐新人编程C/C++语言入门?
- Python序列的切片操作与技巧
- django migration使用指南
- bootstrap按钮加载状态改变
- win7(x64)+VS2012+cocos2d-x环境的配置以及试运行
- ajax跨域传值
- cf C. Inna and Candy Boxes
- The &#39;_imaging&#39; module for the PIL could not be imported: DLL load failed: The specified module could not be found
- hdu 5441 Travel(并查集)
- java中除去字符串(String)中的换行字符(\r \n)
- VPS修改SSH端口不小心把自己给墙掉的一般解决办法
- JDK1.8源码(四)——java.util.Arrays 类
- 基于udp的套接字编程
- 【阿里聚安全&#183;安全周刊】女主换脸人工合成小电影|伊朗间谍APP苹果安卓皆中招
- String工具类2
- noip第27课资料
- vue/cli 3.0 font-size随屏幕大小变化而变化 rem设置
- SQL Server CONVERT() 日期转换为新数据类型的 通用函数