洛谷P3758[TJOI2017]可乐（DP||矩阵优化）

题目链接：https://www.luogu.com.cn/problem/P3758

在不用矩阵优化之前，可以写递推/记忆化：

1 #include
2 #include
3 #include
4 using namespace std;
5 const int N=35;
6 const int maxn=1e6+5;
7 const int mod=2017;
8 int n,m,ans,t;
9 int dp[N][maxn];
10 int head[N],tot;
11 struct node{
12 int to,next;
13 }edge[N<<1];
14 void add(int u,int v){
15 edge[tot].to=v;
16 edge[tot].next=head[u];
17 head[u]=tot++;
18 }
19 int DFS(int u,int t,int f){
20 if(dp[u][t]) return dp[u][t];
21 if(t==1) return 1;
22 dp[u][t]=1;
23 for(int i=head[u];i!=-1;i=edge[i].next){
24 int v=edge[i].to;
25 dp[u][t]+=DFS(v,t-1,u);
26 dp[u][t]%=mod;
27 }
28 dp[u][t]+=DFS(u,t-1,f);
29 dp[u][t]%=mod;
30 return dp[u][t];
31 }
32 int main(){
33 memset(head,-1,sizeof(head));
34 scanf("%d%d",&n,&m);
35 for(int i=1;i<=m;i++){
36 int u,v;
37 scanf("%d%d",&u,&v);
38 add(u,v);
39 add(v,u);
40 }
41 scanf("%d",&t);
42 printf("%d",DFS(1,t+1,0));
43 return 0;
44 }
AC代码

然而这道题可以用矩阵快速幂优化：

用邻接矩阵存图，那么这恰好就是一个矩阵A，矩阵的应用可以求有向图中从a到b经过k条边的可能数。

那么经过t次矩阵乘法，即$A^t$，然后$ans=\sum\limits_{i=0}^n a[1][i]$

（其中b为单元矩阵，即对角线为1，其余为0的矩阵，相当于普通的“1”。）

AC代码：

1 #include
2 #include
3 #include
4 using namespace std;
5 int n,m,t,sum;
6 const int mod=2017;
7 struct Mat{
8 int mat[31][31];
9 Mat(){
10 memset(mat,0,sizeof(mat));
11 }
12 Mat operator*(const Mat &self)const{
13 Mat ans;
14 for(int i=0;i<=30;i++)
15 for(int j=0;j<=30;j++)
16 for(int k=0;k<=30;k++)
17 (ans.mat[i][j]+=mat[i][k]*self.mat[k][j])%=mod;
18 return ans;
19 }
20 }a,b;
21 void init(){
22 for(int i=0;i<=30;i++) b.mat[i][i]=1;//b为单位矩阵
23 }
24 void ksm(int n){
25 while(n){
26 if(n&1) b=b*a;
27 a=a*a;
28 n>>=1;
29 }
30 }
31 int main(){
32 scanf("%d%d",&n,&m);
33 for(int i=1;i<=m;i++){
34 int u,v;
35 scanf("%d%d",&u,&v);
36 a.mat[u][v]=a.mat[v][u]=1;
37 }
38 for(int i=0;i<=n;i++) { a.mat[i][0]=1; a.mat[i][i]=1;}
39 scanf("%d",&t);
40 init();
41 ksm(t);
42 for(int i=0;i<=n;i++) (sum+=b.mat[1][i])%=mod;
43 printf("%d\n",sum);
44 return 0;
45 }
AC代码