矩阵快速幂 HDOJ 5318 The Goddess Of The Moon

  1 /*
  2     DP:：dp[i][k] 表示选择i个字符串，最后一次是k类型的字符串，它由sum (dp[i-1][j]) (a[j], a[k] is ok)累加而来
  3     矩阵快速幂：将n个字符串看成n*n的矩阵，如果匹配，矩阵对应位置为1。矩阵缩短递推dp时间，然后乘m-1次(dp[m][i])累加即可
  4             注意去重
  5     详细解释：http://blog.csdn.net/keshuai19940722/article/details/47111215
  6 */
  7 #include <cstdio>
  8 #include <algorithm>
  9 #include <cstring>
 10 #include <vector>
 11 #include <cmath>
 12 #include <string>
 13 #include <set>
 14 using namespace std;
 15 
 16 typedef long long ll;
 17 const int MAXN = 55;
 18 const int INF = 0x3f3f3f3f;
 19 const int MOD = 1e9 + 7;
 20 struct Mat  {
 21     int m[MAXN][MAXN];
 22     Mat () {
 23         memset (m, 0, sizeof (m));
 24     }
 25     void init(void) {
 26         for (int i=0; i<MAXN; ++i)  m[i][i] = 1;
 27     }
 28 };
 29 int n, m;
 30 int a[MAXN];
 31 int dp[MAXN][MAXN];
 32 
 33 bool judge(int x, int y)    {
 34     char p[15], q[15];
 35     sprintf (p, "%d", x);
 36     sprintf (q, "%d", y);
 37     int lenp =  strlen (p), lenq = strlen (q);
 38     for (int i=0; i<lenp; ++i)  {
 39         int k = 0;
 40         while (i + k < lenp && k < lenq && p[i+k] == q[k])  k++;
 41         if (i + k == lenp && k >= 2)    return true;
 42     }
 43     return false;
 44 }
 45 
 46 Mat operator * (Mat &a, Mat &b) {
 47     Mat ret;
 48     for (int k=1; k<=n; ++k)    {
 49         for (int i=1; i<=n; ++i)    {
 50             for (int j=1; j<=n; ++j)    {
 51                 ret.m[i][j] = (ret.m[i][j] + 1LL * a.m[i][k] * b.m[k][j] % MOD) % MOD;
 52             }
 53         }
 54     }
 55     return ret;
 56 }
 57 
 58 Mat operator ^ (Mat x, int n)   {
 59     Mat ret;    ret.init ();
 60     while (n)   {
 61         if (n & 1)  ret = ret * x;
 62         x = x * x;
 63         n >>= 1;
 64     }
 65     return ret;
 66 }
 67 
 68 Mat work(void)  {
 69     Mat ret;
 70     for (int i=1; i<=n; ++i)    {
 71         for (int j=1; j<=n; ++j)    {
 72             if (judge (a[i], a[j]))   ret.m[i][j] = 1;
 73         }
 74     }
 75     return ret;
 76 }
 77 
 78 void brute_force(void)  {
 79     memset (dp, 0, sizeof (dp));
 80     for (int i=1; i<=n; ++i)    dp[1][i] = 1;
 81     for (int i=2; i<=m; ++i)    {
 82         for (int j=1; j<=n; ++j)    {
 83             for (int k=1; k<=n; ++k)    if (judge (a[j], a[k])) {
 84                 dp[i][k] += dp[i-1][j];
 85                 dp[i][k] %= MOD;
 86             }
 87         } 
 88     }
 89     int res = 0;
 90     for (int i=1; i<=n; ++i)    {
 91         res += dp[m][i];    res %= MOD;
 92     }
 93     printf ("%d\n", res);
 94 }
 95 
 96 int main(void)  {       //HDOJ 5318 The Goddess Of The Moon
 97     int T;  scanf ("%d", &T);
 98     while (T--) {
 99         scanf ("%d%d", &n, &m);
100         for (int i=1; i<=n; ++i)    {
101             scanf ("%d", &a[i]);
102         }
103         sort (a+1, a+1+n);  n = unique (a+1, a+1+n) - (a + 1);
104         
105         //brute_force();
106 
107         Mat x = work ();
108         Mat res = x ^ (m - 1);  int ans = 0;
109         for (int i=1; i<=n; ++i)    {
110             for (int j=1; j<=n; ++j)    {
111                 ans = (ans + res.m[i][j]) % MOD;
112             }
113         }
114         printf ("%d\n", ans);
115     }
116 
117     return 0;
118 }