bzoj 3120 矩阵优化DP
2024-08-26 21:45:54
我的第一道需要程序建矩阵的矩阵优化DP。
题目可以将不同的p分开处理。
对于p==0 || p==1 直接是0或1
对于p>1，就要DP了。这里以p==3为例：
设dp[i][s1][s2][r]为前i列，结尾为0的有s1行（0表示女生，1表示男生），结尾为01的有s2个，结尾为011的有n-s1-s2个，有r列全是1的方案数。
状态这么复杂，看起来一点也不能用矩阵优化，但我们可以将状态(s1,s2,r)hash成整数，然后建立状态之间的转移。
收获：
这种m超过10^7的一般都要用矩阵优化，如果状态很复杂，可以将复杂的状态（但一般不多）hash成整数，然后用计算机建立状态之间的转移，然后就可以用矩阵优化了。
/**************************************************************
Problem: 3120
User: idy002
Language: C++
Result: Accepted
Time:24504 ms
Memory:2616 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#define M 1000000007
#define maxs 200 typedef long long dint; int n, p, q;
dint m;
int comb[][]; void init_comb() {
for( int i=; i<=; i++ )
for( int j=; j<=i; j++ ) {
if( j== || i==j )
comb[i][j]=;
else
comb[i][j] = (comb[i-][j]+comb[i-][j-]);
}
}
struct Matrix {
int n;
dint v[maxs][maxs];
void init( int nn ) {
n=nn;
for( int i=; i<n; i++ )
for( int j=; j<n; j++ )
v[i][j]=;
}
void make_unit( int nn ) {
n=nn;
for( int i=; i<n; i++ )
for( int j=; j<n; j++ )
v[i][j] = i==j;
}
Matrix operator*( const Matrix & b ) const {
const Matrix & a = *this;
Matrix rt;
memset( &rt, , sizeof(rt) );
rt.n = b.n;
for( int k=; k<n; k++ ) {
for( int i=; i<n; i++ ) {
if( a.v[i][k] ) {
for( int j=; j<n; j++ ) {
if( b.v[k][j] ) {
rt.v[i][j] += (a.v[i][k]*b.v[k][j])%M;
if( rt.v[i][j]>=M ) rt.v[i][j]-=M;
}
}
}
}
}
/*
for( int i=0; i<n; i++ ) {
for( int j=0; j<n; j++ ) {
rt.v[i][j] = 0;
for( int k=0; k<n; k++ ) {
rt.v[i][j] += (a.v[i][k]*b.v[k][j])%M;
if( rt.v[i][j]>=M )
rt.v[i][j]-=M;
}
}
}
*/
return rt;
}
}; Matrix mpow( Matrix a, dint b ) {
Matrix rt;
for( rt.make_unit(a.n); b; b>>=,a=a*a )
if( b& ) rt=(rt*a);
return rt;
}
namespace Sec1 {
void sov(){
if( p== ) printf( "0\n" );
else if( p== ) printf( "1\n" );
}
}
namespace Sec2 {
int info[maxs][], idx[][], tot;
Matrix trans;
void init() {
for( int r=; r<=q; r++ )
for( int a=; a<=n; a++ ) {
info[tot][] = a;
info[tot][] = n-a;
info[tot][] = r;
idx[a][r] = tot;
tot++;
}
trans.init(tot);
for( int s=; s<tot; s++ ) {
int a=info[s][], r=info[s][];
for( int sa=; sa<=a; sa++ ) {
int na=n-sa, nr=r+(sa==n);
if( nr>q ) continue;
int ns=idx[na][nr];
trans.v[s][ns] = comb[a][sa];
}
}
}
void sov() {
init();
trans = mpow( trans, m );
int row = idx[n][];
dint ans=;
for( int i=; i<tot; i++ ) {
ans += trans.v[row][i];
if( ans>=M ) ans-=M;
}
printf( "%lld\n", ans );
}
}
namespace Sec3 {
int info[maxs][], idx[][][], tot;
Matrix trans;
void init() {
for( int r=; r<=q; r++ )
for( int a=; a<=n; a++ )
for( int b=; b<=n-a; b++ ) {
info[tot][] = a;
info[tot][] = b;
info[tot][] = n-a-b;
info[tot][] = r;
idx[a][b][r] = tot;
tot++;
}
trans.n = tot;
for( int s=; s<tot; s++ ) {
int a=info[s][], b=info[s][], c=info[s][], r=info[s][];
for( int sa=; sa<=a; sa++ )
for( int sb=; sb<=b; sb++ ) {
int na=c+a-sa+b-sb, nb=sa, nr=r+(sa+sb==n);
if( nr>q ) continue;
int ns = idx[na][nb][nr];
trans.v[s][ns] = comb[a][sa]*comb[b][sb];
}
}
}
void sov(){
init();
trans = mpow( trans, m );
int row = idx[n][][];
dint ans=;
for( int i=; i<tot; i++ ) {
ans += trans.v[row][i];
if( ans>=M ) ans-=M;
}
printf( "%lld\n", ans );
}
} int main() {
scanf( "%d%lld%d%d", &n, &m, &p, &q );
init_comb();
if( p<= ) Sec1::sov();
else if( p== ) Sec2::sov();
else if( p== ) Sec3::sov();
}
最新文章
- 【巩固】JS中的封闭空间
- 036. asp.netWeb用户控件之五使用用户控件实现分页数据导航
- ssh搭建后的简化
- clearfix 清除浮动的问题
- Java再学习——synchronized与volatile
- css3 伪对象选择器添加几何图形文字的方法
- 关于Eclipse平台的使用和开发第一个SWT程序
- C语言中的程序终止函数
- 定义一个runtime的Annotation
- 串匹配模式中的BF算法和KMP算法
- java控制台输入输出
- 工欲善其事，必先利其器之open live writer写作
- 在 JPA、Hibernate 和 Spring 中配置 Ehcache 缓存
- continous integration environment (Jenkins and bitbucket configuration)
- Linux上的10个Touch命令实例
- Select2 4.0.5 API
- shell中打印带有时间的日志的命令（转）
- PSP（4.27——5.3）以及周记录
- Hbase记录-HBase基本操作（一）
- php 文件压缩