請先閱讀Ecrade_的文章中Subtask4,5的思路
題目:P7385 「EZEC-6」跳一跳
此題資料范圍極大，為了優化時間復雜度，采用矩陣快速冪
根據Ecrade_的推理可知:
{
S
[
n
]
=
1
×
S
[
n
?
1
]
+
f
′
[
n
]
+
(
2
b
)
n
f
′
[
n
+
1
]
=
0
×
S
[
n
?
1
]
+
(
a
+
b
)
×
f
′
[
n
]
+
a
×
(
2
b
)
n
(
2
b
)
n
+
1
=
0
×
S
[
n
?
1
]
+
0
×
f
′
[
n
]
+
2
b
×
(
2
b
)
n
\begin{cases}S[n]\ \ \ \ \ \ \ \ =1× S[n-1]+f^{'}[n]+(2b)^n \\ f^{'}[n+1]=0×S[n-1]+(a+b)×f^{'}[n]+a×(2b)^n\\ (2b)^{n+1\ \ \ \ }=0×S[n-1]+0×f^{'}[n]+2b×(2b)^n\end{cases}
??????S[n] =1×S[n?1]+f′[n]+(2b)nf′[n+1]=0×S[n?1]+(a+b)×f′[n]+a×(2b)n(2b)n+1 =0×S[n?1]+0×f′[n]+2b×(2b)n?
得式子:
[
S
[
n
]
f
[
n
+
1
]
(
2
b
)
n
+
1
]
=
[
1
1
1
0
a
+
b
a
0
0
2
b
]
×
[
S
[
n
?
1
]
f
′
[
n
]
(
2
b
)
n
]
\begin{bmatrix}S[n]\\f[n+1]\\(2b)^{n+1} \end{bmatrix}=\begin{bmatrix}1&1&1\\0&a+b&a\\0&0&2b\end{bmatrix}×\begin{bmatrix}S[n-1]\\f^{'}[n]\\(2b)^n\end{bmatrix}
???S[n]f[n+1](2b)n+1????=???100?1a+b0?1a2b????×???S[n?1]f′[n](2b)n????
=
[
1
1
1
0
a
+
b
a
0
0
2
b
]
n
?
1
×
[
S
[
1
]
f
′
[
2
]
(
2
b
)
2
]
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\begin{bmatrix}1&1&1\\0&a+b&a\\0&0&2b\end{bmatrix}^{n-1}×\begin{bmatrix}S[1]\\f^{'}[2]\\(2b)^2\end{bmatrix}
=???100?1a+b0?1a2b????n?1×???S[1]f′[2](2b)2????
設
[
1
1
1
0
a
+
b
a
0
0
2
b
]
\begin{bmatrix}1&1&1\\0&a+b&a\\0&0&2b\end{bmatrix}
???100?1a+b0?1a2b????為
A
A
A,則有
[
S
[
n
]
f
[
n
+
1
]
(
2
b
)
n
+
1
]
=
A
n
×
[
a
+
b
×
2
(
a
+
b
)
×
a
+
a
×
b
×
2
4
b
2
]
\begin{bmatrix}S[n]\\f[n+1]\\(2b)^{n+1} \end{bmatrix}=A^n×\begin{bmatrix}a+b×2\\(a+b)×a+a×b×2\\4b^2\end{bmatrix}
???S[n]f[n+1](2b)n+1????=An×???a+b×2(a+b)×a+a×b×24b2????
用
B
B
B儲存
A
n
A^n
An最終得到式子:
S
[
n
]
=
B
[
1
]
[
1
]
?
(
a
+
b
×
2
)
+
B
[
1
]
[
2
]
[
(
a
+
b
)
×
a
+
a
×
b
×
2
]
+
B
[
1
]
[
2
]
×
4
b
2
S[n]=B[1][1]*(a+b×2)+B[1][2][(a+b)×a+a×b×2]+B[1][2]×4b^2
S[n]=B[1][1]?(a+b×2)+B[1][2][(a+b)×a+a×b×2]+B[1][2]×4b2
Code:
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const ll p=1000000007;
inline ll Read(){
ll dx=0,fh=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
dx=dx*10+c-'0';
c=getchar();
}
return dx*fh;
}
ll quick_pow(ll x,ll y){
ll r=1,base=x,yy=y;
while(y){
if(y&1) r=(r*base)%p;
base=(base*base)%p;
y>>=1;
}
return r%p;
}
ll n,a,b,m,spe;
struct Matricx{
ll val[5][5];
};
Matricx Mul(Matricx x,Matricx y){
Matricx Ans;
for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j){
Ans.val[i][j]=0;
for(int k=1;k<=4;++k) Ans.val[i][j]=(Ans.val[i][j]+((x.val[i][k]%p)*(y.val[k][j]%p))%p)%p;
Ans.val[i][j]%=p;
}
return Ans;
}
Matricx quickpow(Matricx x,ll y){
Matricx r,base=x;
for(int i=1;i<=4;++i){
for(int j=1;j<=4;++j) r.val[i][j]=0;
r.val[i][i]=1;
}
while(y){
if(y&1) r=Mul(r,base);
base=Mul(base,base);
y>>=1;
}
return r;
}
Matricx A,B;
int main(){
n=Read(),a=Read(),b=Read(),m=Read();
a=a*570000004%p,b=b*570000004%p;
for(int i=1;i<=m;++i){
ll spe_num=Read(),spe_score=Read();
spe=(spe+quick_pow(a+b,spe_num-1)*b%p*spe_score%p)%p;
}
A.val[1][1]=1,A.val[1][2]=1,A.val[1][3]=1;
A.val[2][1]=0,A.val[2][2]=a+b,A.val[2][3]=a;
A.val[3][1]=0,A.val[3][2]=0,A.val[3][3]=2*b;
B=quickpow(A,n-1);
ll s1=(a+b*2)%p,f2=( ((a+b)*a)%p + (a*b*2)%p )%p;
printf("%u\n",(((B.val[1][1]*s1%p + B.val[1][2]*f2%p)%p + B.val[1][3]*((4*b*b)%p)%p)%p +spe%p)%p);
return 0;
}
記住打完代碼后一定要檢查一下每個式子有沒有漏取模！本人因為這玩意從早上九點查到了下午三點半！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262475.html
標籤：其他
上一篇：每日小訓練
下一篇：《小學生都能看懂的快速沃爾什變換從入門到升天教程》（FWT / FMT / FMI）（最最嚴謹清晰的證明！零基礎也能得學會！）