规划 一道 矩阵 + 优化 的题目。
题目链接:Luogu P4982。
题目
题目描述
作为吃货的 \(\rm TimeTraveller\),入学的第一件事不是去报到,而是去食堂调查菜品。但是由于各种原因,本学期食堂的菜品很少,而且食堂制定了几天的菜谱,那么这个学期里,以后每天提供的菜品都会按照菜谱轮流循环进行。听到这件事,\(\rm TimeTraveller\) 的内心当然是崩溃的,但是他还是希望每天能吃的不那么重复,于是 \(\rm TimeTraveller\) 决定只要和前一天吃的菜不重复就行了,但是身为吃货的 \(\rm TimeTraveller\) 当然也不想饿肚子,所以每天至少都要吃一道菜。
\(\rm TimeTraveller\) 想要知道他有多少种合法的规划方案,但是他发现这实在是太多了,于是他来求助你,希望你能编写一个程序帮他计算。
数据范围
变量 | 数据范围 |
\(n\) | \(\leq 10^7\) |
\(m\) | \(\leq 7\) |
\(k\) | \(\leq 300\) |
时空限制
题目链接 | 时间限制 | 空间限制 |
Luogu P4982 | \(1\texttt{s}\) | \(7.81\texttt{MiB}\) |
题解
思路
显然是用矩阵快速幂优化递推(动态规划)。但是本题空间很小,不能把所有的矩阵存起来,只能按顺序生成时保存要用的矩阵,其余的都不要了。
另外,本题的转移矩阵很稀疏(绝大多数的数都是 \(0\)),所以可以通过修改矩阵乘法(特判 \(0\))来加速。
这样优化之后,代码的时间复杂度为 \(\Theta(2^{2m}k+2^{3m}\log _ 2\frac{n}{k})\),实际远远跑不满,储存空间只要两个矩阵,空间复杂度为 \(\Theta(2^m)\)。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int mod=1e9+7; const int MAXN=1e7+5; const int MAXM=7; const int MAXK=300+5; const int MAXSIZE=1<<MAXM; inline int add(reg int a,reg int b){ reg int sum=a+b; return sum>=mod?sum-mod:sum; } struct Matrix{ int n,m,unit[MAXSIZE][MAXSIZE]; inline Matrix(void){ n=m=0; return; } inline Matrix(reg int N,reg int M,reg int x=0){ n=N,m=M; for(reg int i=0;i<MAXSIZE;++i) for(reg int j=0;j<MAXSIZE;++j) unit[i][j]=(i==j)?x:0; return; } inline Matrix operator*(const Matrix& a){ Matrix res(n,a.m,0); reg int r; for(reg int i=0;i<n;++i) for(reg int k=0;k<m;++k){ r=unit[i][k]; if(r) for(reg int j=0;j<a.m;++j) if(a.unit[k][j]) res.unit[i][j]=add(res.unit[i][j],1ll*r*a.unit[k][j]%mod); } return res; } inline Matrix operator^(reg int exp){ Matrix res(n,n,1),x=*this; while(exp){ if(exp&1) res=res*x; x=x*x; exp>>=1; } return res; } inline int sum(void){ reg int res=0; for(reg int i=0;i<n;++i) for(reg int j=0;j<m;++j) res=add(res,unit[i][j]); return res; } inline int* operator[](reg int i){ return unit[i]; } }; int n,m,K; int p[MAXK],U[MAXK]; Matrix c,r; int main(void){ n=read(),m=read(),K=read(); for(reg int i=1;i<=K;++i){ p[i]=read(); for(reg int j=1;j<=p[i];++j){ static int x; x=read(); U[i]|=(1<<(x-1)); } } p[K+1]=p[1],U[K+1]=U[1]; reg int size=(1<<m); Matrix start=Matrix(1,size,0); for(reg int S=U[1];S;S=U[1]&(S-1)) ++start[0][S]; --n; reg int chunk=n/K,remain=n-chunk*K; Matrix tmp(size,size,1); for(reg int i=2;i<=remain+1;++i){ static Matrix f; f=Matrix(size,size,0); for(reg int pre=U[i-1];pre;pre=U[i-1]&(pre-1)) for(reg int S=U[i];S;S=U[i]&(S-1)) if(!(S&pre)) ++f[pre][S]; tmp=tmp*f; } r=tmp; for(reg int i=remain+2;i<=K+1;++i){ static Matrix f; f=Matrix(size,size,0); for(reg int pre=U[i-1];pre;pre=U[i-1]&(pre-1)) for(reg int S=U[i];S;S=U[i]&(S-1)) if(!(S&pre)) ++f[pre][S]; tmp=tmp*f; } c=tmp; Matrix ans=start*(c^chunk); if(remain) ans=ans*r; printf("%d\n",ans.sum()); return 0; }
I do not even know how I ended up here, but I thought this
post was great. I do not know who you are but definitely
you’re going to a famous blogger if you aren’t already 😉
Cheers!