2021HDU多校8 - 7057 Buying Snacks(矩阵快速幂套NTT优化dp)

题目链接：点击查看

题目大意：给出 $n$ 种糖果，每种糖果有大小包装之分，有三种购买方案，价钱分别如下：

单独购买一个小的，花费一块钱

单独购买一个大的，花费两块钱

$\forall i>1$，可以和 $i-1$ 的糖果捆绑购买，可以便宜一块钱

问给出的钱在范围 $[0,m]$ 内的不同购买方案数分别是多少

题目分析：

读完题不难想到最简单的 $n^2$ dp，$dp[i][j]$ 代表前 $i$ 个糖果花费了 $j$ 块钱的方案数：$$\begin{gathered} d{p}_{i,j}=d{p}_{i-1,j}+d{p}_{i-1,j-1}+d{p}_{i-1,j-2}+ \\ d{p}_{i-2,j-1}++2d{p}_{i-2,j-2}+d{p}_{i-2,j-3} \end{gathered}$$

$n$ 特别大， 所以考虑矩阵快速幂优化转移。但是众所周知，矩阵快速幂只能优化线性的 $dp$，也就是一维的 $dp$，所以我们需要用生成函数将上面的 $dp$ 方程降维，因为是需要求方案数，所以也算是比较经典的模型了

$$F_i=(1+x+x^2)F_{i-1}+(x+2x^2+x^3)F_{i-2}$$

所以将矩阵快速幂中的矩阵用多项式来表示就可以了，不过如果只是单纯的套上板子会超时，因为一次矩阵乘法需要做 $2\ast 2\ast 2\ast 3=24$ 次 $NTT$，常数巨大，但是不难发现，在矩阵相乘的过程中只涉及到了多项式的乘法和加法，这个用点值表示和用插值表示都是无所谓的，所以我们可以在一开始就将需要相乘的两个矩阵用做 $2\ast 2\ast 2=8$ 次 $NTT$ 转换为点值，中间运算的过程保持点值，最后再将答案矩阵做 $2\ast 2$ 次 $NTT$ 转换为插值返回，这样就能少掉一半的常数，就可以通过本题了

代码：

// Problem: Buying Snacks // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-7057 // Memory Limit: 262 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; const int mod=998244353,G=3,Gi=332748118; typedef vector<int> Poly; int limit,L,r[N],UP; int tmpa[2][2][N],tmpb[2][2][N],tmpc[2][2][N]; int q_pow(int a,int b) {int ans=1;while(b) {if(b&1) ans=1LL*ans*a%mod;a=1LL*a*a%mod,b>>=1;}return ans; } void NTT(int *A,int type) {for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);for(int mid=1;mid<limit;mid<<=1) { int Wn=q_pow(type==1?G:Gi,(mod-1)/(mid<<1));for(int j=0;j<limit;j+=(mid<<1)) {int w=1;for(int k=0;k<mid;k++,w=1LL*w*Wn%mod) {int x=A[j+k],y=1LL*w*A[j+k+mid]%mod;A[j+k]=(x+y)%mod,A[j+k+mid]=(x-y+mod)%mod;}}}if(type==-1) {int inv=q_pow(limit,mod-2);for(int i=0;i<limit;i++) {A[i]=1LL*A[i]*inv%mod;}} } void init(int n,int m) {limit=1;L=0;while(limit<=n+m) limit<<=1,L++;for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1)); } struct Matrix {Poly a[2][2];Poly*operator[](int x) {return a[x];}const Poly*operator[](int x) const {return a[x];}Matrix() {for(int i=0;i<2;i++) {for(int j=0;j<2;j++) {a[i][j]=Poly{};}}}friend Matrix operator * (const Matrix& A,const Matrix& B)//矩阵乘法{Matrix ans;int n=0,m=0;for(int i=0;i<2;i++) for(int j=0;j<2;j++) n=max(n,(int)A[i][j].size());for(int i=0;i<2;i++) for(int j=0;j<2;j++) m=max(m,(int)B[i][j].size());init(n+1,m+1);for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<limit;k++) tmpa[i][j][k]=k<(int)A[i][j].size()?A[i][j][k]:0;for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<limit;k++) tmpb[i][j][k]=k<(int)B[i][j].size()?B[i][j][k]:0;for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<limit;k++) tmpc[i][j][k]=0;for(int i=0;i<2;i++) for(int j=0;j<2;j++) NTT(tmpa[i][j],1),NTT(tmpb[i][j],1);for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) for(int p=0;p<limit;p++) {tmpc[i][j][p]=(tmpc[i][j][p]+1LL*tmpa[i][k][p]*tmpb[k][j][p])%mod;}for(int i=0;i<2;i++) for(int j=0;j<2;j++) NTT(tmpc[i][j],-1);if(limit>UP) {limit=UP;}for(int i=0;i<2;i++) for(int j=0;j<2;j++) {ans[i][j].resize(limit);for(int k=0;k<limit;k++) {ans[i][j][k]=tmpc[i][j][k];}}return ans;}Matrix operator^(int b)//矩阵A的b次方{Matrix ret;for(int i=0;i<2;i++) for(int j=0;j<2;j++) ret[i][j]=i==j?Poly{1}:Poly{}; Matrix A=*this;while(b) { if(b&1) ret=ret*A; A=A*A;b>>=1;}return ret;} }st,tr; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);st[0][0]=Poly{1,1,1};st[0][1]=Poly{1};tr[0][0]=Poly{1,1,1};tr[0][1]=Poly{1};tr[1][0]=Poly{0,1,2,1};int w;cin>>w;while(w--) {int n,m;read(n),read(m);UP=m+1;Poly ans=(st*(tr^(n-1))).a[0][0];for(int i=1;i<=m;i++) {printf("%d ",ans[i]);}puts("");}return 0; }

总结

以上是生活随笔为你收集整理的2021HDU多校8 - 7057 Buying Snacks(矩阵快速幂套NTT优化dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。