[??记录]AT2371 [AGC013E] Placing Squares

**题意** ： 给定一条长为 $n$ 的线段，线段上有 $m$ 个标记点。 将线段切分为若干段，每一段的长度都要是整数，且不能切在标记点上。 设切为 $m$ 段，且第 $i$ 段的长度为 $l_i$ ，则这种切分的权值为 $\prod_{i=1}^ml_i^2$。 求所有合法切分的权值和。答案对 $10^9+7$ 取模。 $n\leq 10^9,m\leq 10^5$ ，时限$\texttt{3s}$。 ------------ 考虑 $\rm DP$。 记 $f[i]$ 为切分 $[0,i]$ 的所有合法方案的权值。 当 $i$ 为标记点， $f[i]=0$。 否则，则有转移 ： $$ \begin{aligned} f[i+1]&=\sum\limits_{j=0}^{i}(i+1-j)^2f[j]\\ &=\sum\limits_{j=0}^{i}\Big((i-j)^2+2(i-j)+1\Big)+f[j]\\ &=\sum\limits_{j=0}^{i}(i-j)^2f[j]+\sum\limits_{j=0}^{i}2(i-j)f[j]+\sum\limits_{j=0}^{i}f[j] \end{aligned} $$ 于是，维护 : $$ \begin{aligned} s_0[i]&=\sum\limits_{j=0}^{i-1}f[j]\\ s_1[i]&=\sum\limits_{j=0}^{i-1}(i-j)f[j]\\ s_2[i]&=\sum\limits_{j=0}^{i-1}(i-j)^2f[j] \end{aligned} $$ 则有 $$ \begin{aligned} f[i]&=s_2[i]\\ s_0[i+1]&=s_0[i]+f[i]=s_2[i]+s_0[i]\\ s_1[i+1]&=\sum\limits_{j=0}^i(i+1-j)f[j]=\sum\limits_{j=0}^{i-1}(i-j)f[j]+\sum\limits_{j=0}^{i}f[j]=s_2[i]+s_1[i]+s_0[i]\\ s_2[i+1]&=f[i+1]=s_2[i]+2s_1[i]+s_0[i+1]=2s_2[i]+2s_1[i]+s_0[i+1]\\ \end{aligned} $$ 当 $i$ 为标记点，有 $$ \begin{aligned} s_2[i+1]&=s_2[i]+2s_1[i]+s_0[i]\\ s_0[i+1]&=s_0[i]\\ s_1[i+1]&=s_1[i]+s_0[i]\\ \end{aligned} $$ 上述转移不难用矩阵描述，使用矩阵快速幂，即可做到 $O(m\log n)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 200500 using namespace std; const int mod=1000000007; struct Mat { int a[3][3]; void I(){ for (int i=0;i<3;i++) for (int j=0;j<3;j++) a[i][j]=(i==j); } Mat operator * (const Mat &B) const { Mat C; for (int i=0;i<3;i++) for (int j=0;j<3;j++){ C.a[i][j]=0; for (int k=0;k<3;k++) C.a[i][j]=(C.a[i][j]+1ll*a[i][k]*B.a[k][j])%mod; } return C; } }; Mat powM(Mat A,int t) { Mat R;R.I(); while(t){ if (t&1)R=R*A; t>>=1;A=A*A; }return R; } int n,m,x[MaxN]; int main() { scanf("%d%d",&n,&m); Mat R,A,B;R.I(); A.a[0][0]=1;A.a[0][1]=1;A.a[0][2]=1; A.a[1][0]=0;A.a[1][1]=1;A.a[1][2]=2; A.a[2][0]=1;A.a[2][1]=1;A.a[2][2]=2; B.a[0][0]=1;B.a[0][1]=1;B.a[0][2]=1; B.a[1][0]=0;B.a[1][1]=1;B.a[1][2]=2; B.a[2][0]=0;B.a[2][1]=0;B.a[2][2]=1; x[0]=-1; for (int i=1;i<=m;i++){ scanf("%d",&x[i]); R=R*powM(A,x[i]-x[i-1]-1)*B; }R=R*powM(A,n-x[m]-1); printf("%d",R.a[0][2]); return 0; } ```