本文主要是介绍uva5318 The Goddess Of The Moon dp+矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dp[i][j]表示前i个以j结尾的方案数，可以由一系列dp[i-1][k]相加得出。类似求斐波那契数的第n项，由于非常大，用矩阵快速幂转移。
import java.io.*;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeSet;public class Main {public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;InputReader in = new InputReader(inputStream);PrintWriter out = new PrintWriter(outputStream);new TaskC().solve(in, out);out.close();}
}class TaskC {static final long mod=1000000007;class Mat {long[][] e=new long[55][55];public Mat pow(long u,int n) {Mat s=new Mat();for(int i=1;i<=n;i++) {s.e[i][i]=1;}Mat q=this;while(u!=0) {if(u%2==1) {s=s.mul(q, n);}q=q.mul(q,n);u=u/2;}return s;}public Mat mul(Mat u,int n) {Mat p=new Mat();for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {p.e[i][j]=0;for(int k=1;k<=n;k++) {p.e[i][j]=(p.e[i][j]+e[i][k]*u.e[k][j]%mod)%mod;}}}return p;}}public void solve(InputReader in,PrintWriter out) {int t=in.nextInt();while(t-->0) {int n=in.nextInt();long m=in.nextLong();long[] d=new long[n+1];TreeSet<Long> se=new TreeSet();for(int i=1;i<=n;i++) {d[i]=in.nextLong();se.add(d[i]);}n=se.size();for(int i=1;i<=n;i++) {d[i]=se.pollFirst();}Mat m1=new Mat();for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {if(good(d[j],d[i])) {m1.e[j][i]=1;}else {m1.e[j][i]=0;}}}Mat m2=new Mat();for(int i=1;i<=n;i++) {m2.e[1][i]=1;}for(int i=2;i<=n;i++) {for(int j=1;j<=n;j++) {m2.e[i][j]=0;}}
// for(int i=1;i<=n;i++) {
// for(int j=1;j<=n;j++) {
// System.out.print(m1.e[i][j]+" ");
// }
// System.out.println();
// }
// for(int i=1;i<=n;i++) {
// for(int j=1;j<=n;j++) {
// System.out.print(m2.e[i][j]+" ");
// }
// System.out.println();
// }Mat m3=m2.mul(m1.pow(m-1,n),n);long ans=0;for(int i=1;i<=n;i++) {ans=(ans+m3.e[1][i])%mod;}out.println(ans);}}boolean good(long l, long m) {String s1=Long.toString(l);String s2=Long.toString(m);for(int i=s1.length()-2;i>=0;i--) {boolean flag=true;if(s1.length()-i>s2.length())return false;for(int k=i,f=0;k<=s1.length()-1;k++,f++) {if(s1.charAt(k)!=s2.charAt(f)) {flag=false;break;}}if(flag)return true;}return false;}}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}
}这篇关于uva5318 The Goddess Of The Moon dp+矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
