杰杰的女性朋友

時間限制：10s????? 空間限制：256MB

題目描述

　 　杰杰是魔法界的一名傳奇人物。他對魔法具有深刻的洞察力，驚人的領悟力，以及令人嘆為觀止的創造力。自從他從事魔法競賽以來，短短幾年時間，就已經成為 世界公認的實力最強的魔法選手之一。更讓人驚嘆的是，他幾乎沒有借助外界力量，完全憑借自己的努力達到了普通人難以企及的高度。在最近的世界魔法奧林匹克 競賽上，他使用高超的魔法本領，一路過關斬將，在最后時刻一舉擊敗了前冠軍“旅行者”，獲得了魔法界最高的榮耀：女神獎杯！女神獎杯可不是一個普通的獎 杯，她能夠幫杰杰實現一個愿望。
　　杰杰本著實事求是的態度，審時度勢，向女神獎杯提出了自己的愿望：想要一個女性朋友。

　　杰杰的愿望實現了，可是女性朋友卻和他不在一個城市。杰杰想要知道：如果要到達女性朋友的所在城市，有多少種方案供他選擇？
　　杰杰所在的世界有n個城市，從1到n進行編號。任意兩個城市都通過有向道路連接。每個城市u有k個入點權：in[u][1],in[u] [2]...in[u][k]，有k個出點權：ou[u][1],ou[u][2]...ou[u][k]。對于任意兩個城市(u,v)（u可以等于 v），u到v的道路條數為(ou[u][1]*in[v][1]+ou[u][2]*in[v][2]+...+ou[u][k]*in[v][k]) 條。杰杰有m次詢問，每次詢問由三元組(u,v,d)構成，詢問從u城市通過不超過d條道路到達v城市的方案數。
　　為了溫柔的杰杰和他的女性朋友的美好未來，幫助他解答這個問題吧。

---

輸入格式

　　第一行讀入兩個正整數n，k，含義如題所示。接下來n行每行2k個整數，第i行代表第i個城市，前k個整數代表i號城市的出點權，后k個整數代表i號城市的入點權：
　　ou[i][1],ou[i][2],…,ou[i][k],in[i][1],in[i][2],…,in[i][k]
　　接下來一個整數m，表示m個詢問。
　　接下來m行，每行三個整數:u,v,d，詢問從u城市通過不超過d條道路到達v城市的方案數。
　　將每個方案所經過的道路，按順序寫成一個序列（序列可以為空）。兩個方案不同，當且僅當他們的道路序列不完全相同。

---

輸出格式

　　對于每個詢問，輸出一個方案數。由于答案可能太大，輸出其除以1000000007后的余數。

---

樣例輸入

5 2 2 5 4 3 7 9 2 4 0 1 5 2 6 3 9 2 2147483647 1000000001 233522 788488 10 1 1 0 2 2 1 2 4 5 4 3 10 3 4 50 1 5 1000 3 5 1000000000 1 2 500000000 4 5 2147483647 3 1 2147483647

---

樣例輸出

1 51 170107227 271772358 34562176 890241289 8516097 383966304 432287042 326522835

---

提示

數據規模和約定
n<=1000
k<=20
m<=50

　　保證1<=u, v<=n, 其它所有讀入為不超過2147483647的非負整數

---

題目來源

By 佚名提供

?FJOI2018一試就是直接使用了這道清華集訓原題。

首先列出DP狀態轉移方程，$f[t][i]$表示走了$t$步之后到達$i$節點的方案數：$$f[t][i]=\sum\limits_{j=1}^{n} (f[t-1][j]*\sum\limits_{l=1}^{k} O_{j,l}*I_{i,l})$$

這樣做的復雜度是$O(n^2d)$，而 $d \leqslant 2^{31}-1$，顯然無法在時限內出解。

觀察這個轉移方程，不難看出這是裸的矩陣快速冪，于是可以在$O(n^3 \log d)$時間內出解。

然而這個復雜度仍然不夠優，事實上，連FJOI2018現場最低的一檔部分分都無法通過。

于是需要進一步觀察矩陣的性質：

$f$是一個$1*n$的矩陣，$O$是一個$n*k$的矩陣，$I$是$n*k$的，而$C=OI^T$所以$C$是$n*n$的。由數據范圍可知，如果我們能將$n*n$的矩陣乘法優化到$k*k$，那么就可以通過全部數據。

不難發現答案$$f[d]=f[0]*C^d=f[0]*(OI^T)^d=f[0]*O*(I^TO)^{d-1}*I$$而$I^TO$是$k*k$的，所以我們只要求$D=I^TO$就好了。

但是還有一個問題，題目要求的是$$\sum\limits_{i=0}^ze8trgl8bvbq f[i]$$ 也就是$$f[0]+f[0]*O{(I^{T}O)}^{0}I +f[0]*O(I^TO)^{1}I+ \ldots +f[0]*O(I^TO)^{d-1}I\\=f[0]*O*(\sum\limits_{i=0}^{d-1}D^{i})*I$$這種涉及到冪和的問題就不能直接使用矩陣快速冪解決。

我們可以首先預處理出所有$A_i=D^{2^i} (i=0,1,2,...)$，$B_i=\sum\limits_{j=1}^{2^i} D^{j} (i=0,1,2,...) $，故$B_i=B_{i-1}A_i$

這樣我們有$$\sum\limits_{i=0}^{d-1}D^{i}=E+(D+D^{1}+...+D^{d_1})+(D^{d_{1}+1}+D^{d_{1}+2}+...+D^{d_1+d_2})+...$$其中$d_i$為d的二進制第i個1代表的數。$E$為單位矩陣

對于每個括號分別考慮，$$D+D^{1}+...+D^{d_1}=B^{d_1}$$$$D^{d_{1}+1}+D^{d_{1}+2}+...+D^{d_1+d_2}=(B_{d_2}*A_{d_1})$$

以此類推，就可以得到最終的答案。代碼片段如下：

rep(i,1,m) rep(j,1,m) B[0][i][j]=A[0][i][j];rep(i,0,L-2){mul(A[i],A[i]);rep(j,1,m) rep(k,1,m) A[i+1][j][k]=C[j][k];rep(j,1,m) up(A[i][j][j],1);mul(B[i],A[i]);rep(j,1,m) rep(k,1,m) B[i+1][j][k]=C[j][k];rep(j,1,m) up(A[i][j][j],P-1);}

?

1 void cal(int n){ 2 rep(i,1,m) rep(j,1,m) G[i][j]=S[i][j]=0; 3 if(n<0)return; 4 rep(i,1,m) S[i][i]=G[i][i]=1; 5 for(int i=0; i<L; i++) if(n>>i&1){ 6 mul(B[i],G); rep(j,1,m) rep(k,1,m) up(S[j][k],C[j][k]); 7 mul(G,A[i]); rep(j,1,m) rep(k,1,m) G[j][k]=C[j][k]; 8 } 9 }

剩下的只要根據輸入數據建矩陣即可

1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 using namespace std; 5 6 const int N=1010,K=21,L=31,P=1000000007; 7 int n,m,q,x,y,z,ans,O[N][K],I[N][K],f[N]; 8 int S[K][K],G[K][K],A[L][K][K],B[L][K][K],C[K][K]; 9 10 void up(int &a,int b){ a+=b; if(a>=P)a-=P; } 11 void mul(int a[][K],int b[][K]){ 12 rep(i,1,m) rep(j,1,m) C[i][j]=0; 13 rep(i,1,m) rep(j,1,m) rep(k,1,m) C[i][k]=(C[i][k]+1ll*a[i][j]*b[j][k])%P; 14 } 15 16 void cal(int n){ 17 rep(i,1,m) rep(j,1,m) G[i][j]=S[i][j]=0; 18 if(n<0)return; 19 rep(i,1,m) S[i][i]=G[i][i]=1; 20 for(int i=0; i<L; i++) if(n>>i&1){ 21 mul(B[i],G); rep(j,1,m) rep(k,1,m) up(S[j][k],C[j][k]); 22 mul(G,A[i]); rep(j,1,m) rep(k,1,m) G[j][k]=C[j][k]; 23 } 24 } 25 26 int main(){ 27 freopen("bzoj3583.in","r",stdin); 28 freopen("bzoj3583.out","w",stdout); 29 scanf("%d%d",&n,&m); 30 rep(i,1,n){ 31 rep(j,1,m) scanf("%d",&O[i][j]); 32 rep(j,1,m) scanf("%d",&I[i][j]); 33 } 34 rep(k,1,n) rep(i,1,m) rep(j,1,m) A[0][i][j]=(A[0][i][j]+1ll*I[k][i]*O[k][j])%P; 35 rep(i,1,m) rep(j,1,m) B[0][i][j]=A[0][i][j]; 36 rep(i,0,L-2){ 37 mul(A[i],A[i]); 38 rep(j,1,m) rep(k,1,m) A[i+1][j][k]=C[j][k]; 39 rep(j,1,m) up(A[i][j][j],1); 40 mul(B[i],A[i]); 41 rep(j,1,m) rep(k,1,m) B[i+1][j][k]=C[j][k]; 42 rep(j,1,m) up(A[i][j][j],P-1); 43 } 44 scanf("%d",&q); 45 while (q--){ 46 scanf("%d%d%d",&x,&y,&z); cal(z-1); 47 rep(i,1,m) f[i]=0; ans=0; 48 rep(i,1,m) rep(j,1,m) f[i]=(f[i]+1ll*O[x][j]*S[j][i])%P; 49 rep(i,1,m) ans=(ans+1ll*f[i]*I[y][i])%P; 50 printf("%d\n",(ans+(x==y))%P); 51 } 52 return 0; 53 }

?

?

?

?

?

轉載于:https://www.cnblogs.com/HocRiser/p/8453579.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[BZOJ3583]杰杰的女性朋友(矩阵快速幂)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。