HDU - 2604 矩阵快速幂 字符串递推 两种解法
2024-08-24 03:52:02
记dp[i]为长度i且符合题意的方案数,dp[n]就是解
符合方案的是不含fmf和fff子串的字符串
考虑如何从前面几项递推出后面第i项
(★表示存在生成的非法方案)←其实没啥用处
i=1时
m③ f③
i=2时
mm② mf② fm★② ff★②
i=3时
mmm mmf mfm★ mff★ fmm ffm★
i=4时
mmmm① mmmf① mmfm★① mmff★① mfmm① mffm★① fmmm① fmmf① ffmm①
i=5时
mmmmm① mmmmf② mmmfm① mmmff③ mmfmm① mmffm① mfmmm① mfmmf② mffmm① fmmmm① fmmmf② fmmfm① fmmff③ ffmmm① ffmmf②
i=5时,考虑第i-1项,其中所有方案接m都可以转移①
考虑第i-2项,只可以接_f形式,由★可得出无论是mf还是ff都有非法方案存在的结论,无法转移
考虑第i-3项,可以接__f形式 mmf可以②,mff非法,f_f非法
考虑第i-4项,只剩下mmff形式③
所有生成的第五项的串全部转移完毕,得到dp(n)=dp(n-1)+dp(n-3)+dp(n-4)
/*H E A D*/
int MOD = 9973;
inline ll mod(ll a){return a%MOD;}
struct Matrix{
ll mt[22][22],r,c;
void init(int rr,int cc,bool flag=0){
r=rr;c=cc;
memset(mt,0,sizeof mt);
if(flag) rep(i,1,r) mt[i][i]=1;
}
Matrix operator * (const Matrix &rhs)const{
Matrix ans; ans.init(r,rhs.c);
rep(i,1,r){
rep(j,1,rhs.c){
int t=max(r,rhs.c);
rep(k,1,t){
ans.mt[i][j]+=mod(mt[i][k]*rhs.mt[k][j]);
ans.mt[i][j]=mod(ans.mt[i][j]);
}
}
}
return ans;
}
};
Matrix fpw(Matrix A,int n){
Matrix ans;ans.init(A.r,A.c,1);
while(n){
if(n&1) ans=ans*A;
n>>=1;
A=A*A;
}
return ans;
}
int bas[5][5]={
{0,0,0,0,0},
{0,1,0,1,1},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0},
};
int bas2[5]={0,9,6,4,2};
int main(){
int n,m;
Matrix A;A.init(4,4);
rep(i,1,4) rep(j,1,4) A.mt[i][j]=bas[i][j];
Matrix b; b.init(4,1);
rep(i,1,4) b.mt[i][1]=bas2[i];
while(cin>>n>>m){
MOD=m;
if(n<=3){
println(b.mt[5-n][1]%MOD);
continue;
}
Matrix res=fpw(A,n-4); res=res*b;
ll ans=mod(res.mt[1][1]+m);
println(ans);
}
return 0;
}
解法二:
很显然不断拼接枚举简直累死人,干嘛不直接把三位的子串全部递推出来
注意fmf和fff递推时强制设0表示非法方案
保险起见还是设递推项为第五项开始
时间复杂度较高,不过依然能AC
/*H E A D*/
int MOD = 9973;
inline ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll mod(ll a){return a%MOD;}
struct Matrix{
ll mt[22][22],r,c;
void init(int rr,int cc,bool flag=0){
r=rr;c=cc;
memset(mt,0,sizeof mt);
if(flag) rep(i,1,r) mt[i][i]=1;
}
Matrix operator * (const Matrix &rhs)const{
Matrix ans; ans.init(r,rhs.c);
rep(i,1,r){
rep(j,1,rhs.c){
int t=max(r,rhs.c);
rep(k,1,t){
ans.mt[i][j]+=mod(mt[i][k]*rhs.mt[k][j]);
ans.mt[i][j]=mod(ans.mt[i][j]);
}
}
}
return ans;
}
};
Matrix fpw(Matrix A,int n){
Matrix ans;ans.init(A.r,A.c,1);
while(n){
if(n&1) ans=ans*A;
n>>=1;
A=A*A;
}
return ans;
}
// 4 7 -> 9->O fff_(m|f) fmf_(m|f) fff fmf
//dp[1][i]:fff dp[1][i+1]=0dp[1][i]+0dp[2][i] 0
//dp[2][i]:mff dp[2][i+1]=dp[3][i]+dp[5][i] 2
//dp[3][i]:fmf dp[3][i+1]=0dp[4][i]+0dp[6][i] 0
//dp[4][i]:ffm dp[4][i+1]=dp[1][i]+dp[2][i] 1
//dp[5][i]:mmf dp[5][i+1]=dp[7][i]+dp[8][i] 4
//dp[6][i]:mfm dp[6][i+1]=dp[3][i]+dp[5][i] 2
//dp[7][i]:fmm dp[7][i+1]=dp[4][i]+dp[6][i] 2
//dp[8][i]:mmm dp[8][i+1]=dp[7][i]+dp[8][i] 4
int bas[9][9]={
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,1,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,1},
{0,0,0,1,0,1,0,0,0},
{0,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,0,1,1},
};
int bas2[9]={0,0,2,0,1,4,2,2,4};
int main(){
int n,m;
Matrix A;A.init(8,8);
rep(i,1,8) rep(j,1,8) A.mt[i][j]=bas[i][j];
Matrix b; b.init(8,1);
rep(i,1,8) b.mt[i][1]=bas2[i];
while(cin>>n>>m){
MOD=m;
if(n<=4){
switch(n){
case 0 :println(0%MOD);break;
case 1 :println(2%MOD);break;
case 2 :println(4%MOD);break;
case 3 :println(6%MOD);break;
case 4 :println(9%MOD);break;
}
continue;
}
Matrix res=fpw(A,n-5); res=res*b;
ll ans=0;
// rep(i,1,8) cout<<res.mt[i][1]<<" ";cout<<endl;
rep(i,1,8) ans=mod(ans+res.mt[i][1]+m);
println(ans);
}
return 0;
}
最新文章
- Redis指南
- SQLAchemy
- XE8 (RTM) Android SDK 更新安装（转）
- 清空文件下的SVN控制文件
- VHDL：信号、端口以及和Verilog的区别
- QTableWidget实用技巧（转）
- python文件选择：tkFileDialog 基础
- Swing应用开发实战系列之四：组件内容实时刷新问题
- Windows下一些配置信息
- eclipse 中提示tomcat 的端口被占用了 后的最快捷解决方法
- Jquery库及其他库之间的$命名冲突解决办法
- javascript正则表达式 —— RegExp 对象
- 分布式拒绝服务攻击(DDoS)原理及防范【转】
- android 百度最新地图sdk包怎么去除 放大缩小按钮
- Python 3
- python 基础学习小记
- PyQt4 的事件与信号 -- 发射信号
- IntelliJ IDEA 2016.2.x 激活
- Struts 2 之 OGNL
- U盘权限不足，只读文件系统