Loading... ## 题意 给定一个长为 $n$ 的线段，要把线段划分成若干长度为正整数的段，但是有 $m$ 个地方不能划分，每种划分的权值定义为每一段长度的平方求积，求每一种情况的权值和。 $n\leq 10^9,m\leq 10^5$ ## 题解 首先把每一段平方值这个东西转化了，设长度为 $l$，那么 $l^2$ 的组合意义就是，在一个长度为 $l$ 的线段上选有顺序选某一段放放黑球或者白球，两个球可以重合。然后就好做了，设 $dp_{i,j},j\in[0,2]$ 表示当前考虑了前 $i$ 长度的线段，最后一段已经选了 $j$ 个点的方案数，对于可以在第 $i$ 个点划分的情况转移是： - $dp_{i+1,0}=dp_{i,0}+dp_{i,2}$，意义分别是划分或者不划分。 - $dp_{i+1,1}=dp_{i,0}+dp_{i,0}+dp_{i,1}+dp_{i,2}+dp_{i,2}$，意义分别是放黑球、放白球、不放也不划分、划分并且放黑球、划分并且放白球。 - $dp_{i+1,2}=dp_{i,0}+dp_{i,1}+dp_{i,2}+dp_{i,2}$，意义分别是放黑球和白球、放还没放的球、不放也不划分、划分并且放黑球和白球。 若不能划分同理： - $dp_{i+1,0}=dp_{i,0}$ - $dp_{i+1,1}=dp_{i,0}+dp_{i,0}+dp_{i,1}$ - $dp_{i+1,2}=dp_{i,0}+dp_{i,1}+dp_{i,2}$ 发现大量转移本质相同，那么对于两个不能划分的点中间用矩阵快速幂转移，然后不能划分的点转移一步继续计算即可。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} const long long mod=1000000007; #define MATRIX_MOD %mod #define MATRIX_DATA_TYPE long long const int MATRIX_MAX_N=3; const int MATRIX_MAX_M=3; struct MATRIX{ int n,m; MATRIX_DATA_TYPE matrix[MATRIX_MAX_N][MATRIX_MAX_M]; MATRIX operator + (const MATRIX &a) const { register int i,j; MATRIX ans; ans.n=n; ans.m=m; for(i=0;i<n;++i) for(j=0;j<m;++j) ans.matrix[i][j]=(matrix[i][j]+a.matrix[i][j])MATRIX_MOD; return ans; } MATRIX operator * (const MATRIX &a) const { register int i,j,k; MATRIX ans; ans.n=n; ans.m=a.m; for(i=0;i<n;++i) for(j=0;j<a.m;++j){ ans.matrix[i][j]=0; for(k=0;k<m;++k) ans.matrix[i][j]=(ans.matrix[i][j]+matrix[i][k]*a.matrix[k][j]MATRIX_MOD)MATRIX_MOD; } return ans; } friend MATRIX operator ^ (MATRIX base,register MATRIX_DATA_TYPE exponential){ register int i,j; MATRIX ans; ans.n=base.n; ans.m=base.n; for(i=0;i<ans.n;++i) for(j=0;j<ans.m;++j) ans.matrix[i][j]=(i==j); while(exponential){ if(exponential&1) ans=ans*base; base=base*base; exponential>>=1; } return ans; } void clear(){ register int i,j; for(i=0;i<n;++i) for(j=0;j<m;++j) matrix[i][j]=0; return; } }base,trans1,trans2; int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,lat=-1,now; int n=read(); int m=read(); base.n=base.m=3; trans1=trans2=base; base.matrix[0][0]=1,base.matrix[0][1]=0,base.matrix[0][2]=0; trans1.matrix[0][0]=1,trans1.matrix[0][1]=2,trans1.matrix[0][2]=1; trans1.matrix[1][0]=0,trans1.matrix[1][1]=1,trans1.matrix[1][2]=1; trans1.matrix[2][0]=1,trans1.matrix[2][1]=2,trans1.matrix[2][2]=2; trans2.matrix[0][0]=1,trans2.matrix[0][1]=2,trans2.matrix[0][2]=1; trans2.matrix[1][0]=0,trans2.matrix[1][1]=1,trans2.matrix[1][2]=1; trans2.matrix[2][0]=0,trans2.matrix[2][1]=0,trans2.matrix[2][2]=1; for(i=0;i<m;++i){ now=read(); base=base*(trans1^(now-lat-1)); base=base*trans2; lat=now; } base=base*(trans1^(n-lat-1)); print(base.matrix[0][2]); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 04 月 21 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏