HDU 2604 Queuing（ 递推关系 + 矩阵快速幂 ）
2024-08-26 02:44:54
链接：传送门
题意：一个队列是由字母 f 和 m 组成的，队列长度为 L，那么这个队列的排列数为 2^L 现在定义一个E-queue，即队列排列中是不含有 fmf or fff ，然后问长度为L的E-queue的个数 % M
思路：
这道题的关键是找到递推关系！递推关系为：Fn = Fn-1 + Fn-3 + Fn-4，与HDU1575简直一模一样，然后直接矩阵快速幂就OK了
递推关系式不好找，我们可以将字母 f m 分别看为 1 0，给出一个长度L，排列数是为 2^L ，可以把它简单看作一个二进制数，L = 3 时这个队列的排列情况就是数 [ 0 ～ 2^3 ] ，可以写出来看看
L = 3
- 0 0 0 , 0 0 1 , 0 1 0 , 0 1 1 , 1 0 0 , 1 0 1 , 1 1 0 , 1 1 1，不符合要求的是 1 0 1 & 1 1 1，所以 L = 3 时 E-queue 为 6
L = 4，可以认为是 2^3 * 2^ 3
- 0 0 0 0 , 0 0 0 1 , 0 0 1 0 , 0 0 1 1 , 0 1 0 0 , 0 1 0 1 , 0 1 1 0 , 0 1 1 1
- 1 0 0 0 , 1 0 0 1 , 1 0 1 0 , 1 0 1 1 , 1 1 0 0 , 1 1 0 1 , 1 1 1 0 , 1 1 1 1
可以看出是 L = 3 的情况在前面分别加上 0 1 ，加上 0 是不影响 E-queue 的个数的 ， 所以 L = 4 答案的来源 是 L = 3 和其他来源，后来写出了L = 5 和 L = 6 时候的答案，发现 Fn = Fn-1 + Fn-3 + Fn-4 （ n 相当于 L ），具体为什么为还没有得到一种比较合理的解释，过段时间再补吧......递推关系的寻找还是相当重要的...... 我真是菜的扣脚...... 还是蒟蒻
/*************************************************************************
> File Name: hdu2604.cpp
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年05月03日 星期三 18时30分45秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
int MOD;
const int maxn = 4;
#define ll long long
#define mod(x) ((x)%MOD)
struct mat{
int m[maxn][maxn];
}unit;
mat operator *(mat a,mat b){
mat ret;
ll x;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
x = 0;
for(int k=0;k<4;k++)
x += mod( (ll)a.m[i][k]*b.m[k][j] );
ret.m[i][j] = x;
}
}
return ret;
}
void init_unit(){
for(int i=0;i<maxn;i++) unit.m[i][i] = 1;
return;
}
mat pow_mat(mat a,ll x){
mat ret = unit;
while(x){
if(x&1) ret = ret*a;
a = a*a;
x >>= 1;
}
return ret;
}
mat a,b;
void init(){
memset(a.m,0,sizeof(a.m));
memset(b.m,0,sizeof(b.m));
a.m[0][0] = a.m[0][2] = a.m[0][3] = 1;
a.m[1][0] = a.m[2][1] = a.m[3][2] = 1;
b.m[0][0] = 9; b.m[1][0] = 6;
b.m[2][0] = 4; b.m[3][0] = 2;
}
int main(){
init();
init_unit();
int ss[4] = {2,4,6,9};
int n;
while(~scanf("%d%d",&n,&MOD)){
if(n<5) printf("%d\n",ss[n-1]%MOD);
else{
mat ans = pow_mat(a,n-4);
ans = ans*b;
printf("%d\n",ans.m[0][0]%MOD);
}
}
return 0;
}最新文章
- bzoj[3238][ahoi差异]
- 借用Snippet插件美化博客中的代码
- css的小问题总结
- 表数据文件DBF的读取和写入操作
- Java日志记录的事儿
- C#_自动化测试3_controll IE
- java中调用js脚本
- Spring配置多数据源错误总结
- php 备份和还原数据库
- VM虚拟机下CentOS 6.5配置IP地址的三种方法
- linux下安装php的mcrypt拓展
- PowerShell安全修改Windows 10 登陆背景图
- 截取字段split
- 干了这碗鸡汤：从理发店小弟到阿里P10技术大牛
- [转] webpack之前端性能优化（史上最全，不断更新中。。。）
- UVALive - 7637 E - Balanced String(构造)
- android编译错误--/usr/bin/ld: cannot find -lz
- [js]this和call.call
- mysql的sql执行计划详解
- Xamarin iOS教程之键盘的使用和设置