[HDU2604]Queuing
题目:Queuing
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2604
分析:
1)将当前格和上一格合并当作一个状态,考虑下一个格子放0(m)还是1(f).
构造转移矩阵
$\left[ \begin{array}{ccccc} . & 00 & 01 & 10 & 11 \\ 00 & 1 & 1 & 0 & 0 \\ 01 & 0 & 0 & 1 & 1 \\ 10 & 1 & 0 & 0 & 0 \\ 11 & 0 & 0 & 1 & 0 \end{array} \right] $
2)假设第一格前还有两格,为00。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
int MOD;
struct Matrix{
LL a[][];
void init(int f){
memset(a,,sizeof a);
if(f==-)return;
for(int i=;i<;++i)a[i][i]=;
}
};
Matrix operator*(Matrix& A,Matrix& B){
Matrix C;C.init(-);
for(int i=;i<;++i)
for(int j=;j<;++j)
for(int k=;k<;++k){
C.a[i][j]+=A.a[i][k]*B.a[k][j];
C.a[i][j]%=MOD;
}
return C;
}
Matrix operator^(Matrix A,int n){
Matrix Rt;Rt.init();
for(;n;n>>=){
if(n&)Rt=Rt*A;
A=A*A;
}
return Rt;
}
int main(){
int n;
Matrix A,T;
T.a[][]=T.a[][]=;T.a[][]=T.a[][]=;
T.a[][]=T.a[][]=;T.a[][]=T.a[][]=;
T.a[][]=;T.a[][]=T.a[][]=T.a[][]=;
T.a[][]=T.a[][]=;T.a[][]=;T.a[][]=;
for(;~scanf("%d%d",&n,&MOD);){
A=T^n;
LL ans=A.a[][]+A.a[][]+A.a[][]+A.a[][];
printf("%lld\n",ans%MOD);
} return ;
}
学到了一种很有趣的递推思路。
3)设f(i)为字符串长度为i时符合条件的字符串个数。枚举最后几位字符。
4)当最后一个字符为0 (m)时前n-1个字符没有限制,即为f(n-1);
当最后一个字符为1(f)时要考虑不满足的情况,那考虑最后两个字符为01(mf)和11(ff)的情况,显然要继续考虑。最后3个字符为101(fmf)、111(fff)显然不满足条件,最后3个字符为001(mmf),前n-3个字符没有限制,最后三个字符为011则要继续考虑,最后四个字符为0011,前n-4个字符没有限制,最后4个字符为1011不满足条件。综上f(n)=f(n-1)+f(n-3)+f(n-4)
数列:f(0)=1、f(1)=2、f(2)=4、f(3)=6、f(4)=9、f(5)=15 ...
添加一下:f(-1)=1、f(-2)=1、f(-3)=0;
5)构造矩阵
$\left[ \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right] $
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
int MOD;
struct Matrix{
LL a[][];
void init(int f){
memset(a,,sizeof a);
if(f==-)return;
for(int i=;i<;++i)a[i][i]=;
}
};
Matrix operator*(Matrix& A,Matrix& B){
Matrix C;C.init(-);
for(int i=;i<;++i)
for(int j=;j<;++j)
for(int k=;k<;++k){
C.a[i][j]+=A.a[i][k]*B.a[k][j];
C.a[i][j]%=MOD;
}
return C;
}
Matrix operator^(Matrix A,int n){
Matrix Rt;Rt.init();
for(;n;n>>=){
if(n&)Rt=Rt*A;
A=A*A;
}
return Rt;
}
int main(){
int n;
Matrix A,T;
T.a[][]=T.a[][]=T.a[][]=;T.a[][]=;
T.a[][]=;T.a[][]=T.a[][]=;T.a[][]=;
T.a[][]=;T.a[][]=;T.a[][]=T.a[][]=;
T.a[][]=T.a[][]=;T.a[][]=T.a[][]=;
for(;~scanf("%d%d",&n,&MOD);){
A=T^n;
LL ans=A.a[][]+A.a[][]+A.a[][];
printf("%lld\n",ans%MOD);
} return ;
}
最新文章
- HTML JQuery 技巧总结
- android 命令行
- ubuntu 14 配置JDK
- Xcode7创建的项目添加启动图有问题?
- Sql之表的连接总结
- 清风注解-Swift程序设计语言:Point1~5
- FLUSH TABLES WITH READ LOCK 锁全局
- 业务逻辑 : forex &; mlm
- 51Nod 1326 遥远的旅途
- 水晶报表使用IEnumerable<;T>;数据源
- 第五章 动态SQL 批量操作
- Python11/12--GIL/互斥锁/进程池
- Windows 10忘记登录密码不用怕,系统U盘/光盘轻松重置
- Django:管理站点
- iOS之分类(category)
- 35.在CSS中 只用一个 DOM 元素就能画出国宝熊猫
- vc读取当前路径和读取配置ini文件
- jQuery基础笔记(2)
- STM32标准外设库、 HAL库、LL库
- C#:消息框
热门文章
- SPSS输出结果如何在word中设置小数点前面显示加0
- javascript获取select 的id与值
- 洛谷T89643 escape
- Activation Functions and Their Derivatives
- MySQL点滴记录
- js 解决函数加载的问题
- [Bzoj3224][Tyvj1728] 普通平衡树(splay/无旋Treap)
- 【学习总结】Python-3-字符串函数split()的妙用
- k3 cloud成本调整单引入单据后,再做出库成本核算。成本调整单列表已审核的单据消失,非已审核的单据还在,这是出库成本核算设置参数的问题吗?
- C#实现百度ping功能