省选模拟赛 Problem 3. count (矩阵快速幂优化DP)

Discription

DarrellDarrellDarrell 在思考一道计算题。

给你一个尺寸为 1×N1 × N1×N 的长条,你可以在上面切很多刀,要求竖直地切并且且完后每块的长度都是整数。

在这种限制下其实只有 N−1N − 1N−1 个位置可以切。

对于一种切的方案,假如切完后每块的宽度分别是:w1,w2,w3,...,wk(∑wi=N)w_1, w_2, w_3, ..., w_k(\sum w_i = N)w1​,w2​,w3​,...,wk​(∑wi​=N),那么该种方案对应

的完美值为:∏i=1kwi2
∏^{k}_{i=1}w_i^2i=1∏k​wi2​

那么问题来了,给出 MMM 个位置不能切(如果用 xxx 表示一个位置,那么切完该位置后长条变为 1×x1 × x1×x 和

1×(N−x)1 × (N − x)1×(N−x) 两块),那么所有合法切法对应的完美值的和是多少呢?(只需要输出模 109+710^9 + 7109+7 的结果)

Input

第 111 行,有 222 个整数:NMN MNM,表示长条的总长度及不能切的位置数

第 222 行,有 MMM 个整数:x1,x2,x3,...,xMx_1, x_2, x_3, ..., x_Mx1​,x2​,x3​,...,xM​ 表示不能切的位置。

Output

输出 111 行,包含 111 个整数,表示满足要求的所有切法对应的完美值和。(对 109+710^9 + 7109+7 取模后的结果)

Note

• 对于 20%20\%20% 的数据,有 1≤N,M≤1031 ≤ N, M ≤ 10^31≤N,M≤103。

• 对于 60%60\%60% 的数据,有 1≤N,M≤1051 ≤ N, M ≤ 10^51≤N,M≤105。

• 对于 100%100\%100% 的数据,有 1≤N≤109,1≤M≤1051 ≤ N ≤ 10^9,1 ≤ M ≤ 10^51≤N≤109,1≤M≤105,且 1≤x1&lt;x2&lt;x3&lt;...&lt;xm&lt;N1 ≤ x_1 &lt; x_2 &lt; x_3 &lt; ... &lt; x_m &lt; N1≤x1​<x2​<x3​<...<xm​<N


很显然可以看出DPDPDP柿子dp[0]=1,   dp[i]=∑j=0i−1dp[j]∗(i−j)2dp[0]=1,\ \ \ dp[i]=\sum_{j=0}^{i-1}dp[j]*(i-j)^2dp[0]=1,   dp[i]=j=0∑i−1​dp[j]∗(i−j)2

然后答案就为dp[N]dp[N]dp[N]

由于NNN很大 ≤109\le10^9≤109

所以考虑用矩阵快速幂优化转移

先想想M=0M=0M=0怎么转移

定义向量如下:[   ∑j=0idp[j] , ∑j=0idp[j]∗(i−j) , ∑j=0idp[j]∗(i−j)2   ]\left[\ \ \ \sum_{j=0}^idp[j]\ ,\ \sum_{j=0}^idp[j]*(i-j)\ ,\ \sum_{j=0}^idp[j]*(i-j)^2\ \ \ \right][   j=0∑i​dp[j] , j=0∑i​dp[j]∗(i−j) , j=0∑i​dp[j]∗(i−j)2   ]

然后考虑从[   ∑j=0i−1dp[j] , ∑j=0i−1dp[j]∗(i−1−j) , ∑j=0i−1dp[j]∗(i−1−j)2   ]\left[\ \ \ \sum_{j=0}^{i-1}dp[j]\ ,\ \sum_{j=0}^{i-1}dp[j]*(i-1-j)\ ,\ \sum_{j=0}^{i-1}dp[j]*(i-1-j)^2\ \ \ \right][   j=0∑i−1​dp[j] , j=0∑i−1​dp[j]∗(i−1−j) , j=0∑i−1​dp[j]∗(i−1−j)2   ]转移到[   ∑j=0idp[j] , ∑j=0idp[j]∗(i−j) , ∑j=0idp[j]∗(i−j)2   ]\left[\ \ \ \sum_{j=0}^idp[j]\ ,\ \sum_{j=0}^idp[j]*(i-j)\ ,\ \sum_{j=0}^idp[j]*(i-j)^2\ \ \ \right][   j=0∑i​dp[j] , j=0∑i​dp[j]∗(i−j) , j=0∑i​dp[j]∗(i−j)2   ]

转移矩阵就是

[221110121][∑j=0i−1dp[j]∑j=0i−1dp[j]∗(i−1−j)∑j=0i−1dp[j]∗(i−1−j)2]=[∑j=0idp[j]∑j=0idp[j]∗(i−j)∑j=0idp[j]∗(i−j)2]\left[\begin{matrix}
2&amp;2&amp;1\\
1&amp;1&amp;0\\
1&amp;2&amp;1\\
\end{matrix}\right]
\left[\begin{matrix}
\sum_{j=0}^{i-1}dp[j]\\
\sum_{j=0}^{i-1}dp[j]*(i-1-j)\\
\sum_{j=0}^{i-1}dp[j]*(i-1-j)^2\\
\end{matrix}\right]
=\left[\begin{matrix}
\sum_{j=0}^{i}dp[j]\\
\sum_{j=0}^{i}dp[j]*(i-j)\\
\sum_{j=0}^{i}dp[j]*(i-j)^2\\
\end{matrix}\right]
⎣⎡​211​212​101​⎦⎤​⎣⎢⎡​∑j=0i−1​dp[j]∑j=0i−1​dp[j]∗(i−1−j)∑j=0i−1​dp[j]∗(i−1−j)2​⎦⎥⎤​=⎣⎢⎡​∑j=0i​dp[j]∑j=0i​dp[j]∗(i−j)∑j=0i​dp[j]∗(i−j)2​⎦⎥⎤​自己推一推吧…

注意第二项和第三项当j=ij=ij=i时贡献的值是000因为i−j=0i-j=0i−j=0,所以jjj的范围实质上是[0,i−1][0,i-1][0,i−1].为了统一就写成[0,i][0,i][0,i]了.

考虑这个地方不能切,我们就强制把这个位置的dpdpdp值设为000就行了.

那么不能切的地方的转移,就只用把第一项累加dp[i]dp[i]dp[i]的系数去掉就行了.第一行也就变成了[2,2,1]−[1,2,1]=[1,0,0][2,2,1]-[1,2,1]=[1,0,0][2,2,1]−[1,2,1]=[1,0,0],那么不能切的地方的转移矩阵就如下:

[100110121]\left[\begin{matrix}
1&amp;0&amp;0\\
1&amp;1&amp;0\\
1&amp;2&amp;1\\
\end{matrix}\right]⎣⎡​111​012​001​⎦⎤​

详细见代码

CODE

#include<bits/stdc++.h>
using namespace std;
inline void read(int &num) {
char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg = -flg;
for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar()); num*=flg;
}
const int MAXN = 1e5+5;
const int mod = 1e9+7;
struct mat {
int a[3][3];
mat() { memset(a,0,sizeof a); }
inline void init1() {
a[0][0] = 2; a[0][1] = 2; a[0][2] = 1;
a[1][0] = 1; a[1][1] = 1; a[1][2] = 0;
a[2][0] = 1; a[2][1] = 2; a[2][2] = 1;
}
inline void init2() {
a[0][0] = 1; a[0][1] = 0; a[0][2] = 0;
a[1][0] = 1; a[1][1] = 1; a[1][2] = 0;
a[2][0] = 1; a[2][1] = 2; a[2][2] = 1;
}
inline mat operator *(const mat &o)const {
mat re;
for(int k = 0; k < 3; ++k)
for(int i = 0; i < 3; ++i) if(a[i][k])
for(int j = 0; j < 3; ++j) if(o.a[k][j])
re.a[i][j] = (re.a[i][j] + 1ll * a[i][k] * o.a[k][j] % mod) % mod;
return re;
}
inline mat operator ^(int b)const {
mat A = *this, re;
re.a[0][0] = re.a[1][1] = re.a[2][2] = 1;
while(b) {
if(b & 1) re = re * A;
A = A * A; b >>= 1;
}
return re;
}
}ans, trans1, trans2;
int N, M, pos[MAXN];
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; ++i)
scanf("%d", &pos[i]);
ans.a[0][0] = 1;
trans1.init1();
trans2.init2();
for(int i = 1; i <= M; ++i)
ans = (trans1^(pos[i]-pos[i-1]-1)) * ans, ans = trans2 * ans;
ans = (trans1^(N-pos[M])) * ans;
printf("%d\n", ans.a[2][0]);
}

妈妈我终于会矩阵快速幂了!!!

上一篇:WPF快速精通版


下一篇:HIVE扩展GIS函数