Codeforces 621E—Wet Shark and Blocks（数位DP+矩阵快速幂优化）

题意：一个b位的数Y,每一位的数可以从题目给的n个数里面选，问有多少种方案使得Y mod x == k？

思路：数位dp，另dp[i][k]表示前i位模x结果为k的方案数，则转移方程为：dp[i][(k*10+j)%x]+=dp[i-1][k]*num[j]（0<=j<=9），num[j]为题目所给数据j的个数。显然一维高达1e9没法正常递推，所以用矩阵快速幂优化。构造一个100*100的初始矩阵，第一行代表第一位%x等于j的方案数（0<=j<=99），接下来是构造矩阵，矩阵的规模也是100*100。假设(i*10+j)%x=now,(0<=i<=99,0<=j<=9),那么取下一位后的结果是now的增加的方案数就是满足条件的num[j]的和。

Codeforces 621E—Wet Shark and Blocks（数位DP+矩阵快速幂优化）

 1 #include <iostream>
 2 #include <queue>
 3 #include <stack>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <map>
 7 #include <set>
 8 #include <bitset>
 9 #include <algorithm>
10 #include <cmath>
11 #include <cstring>
12 #include <cstdlib>
13 #include <string>
14 #include <sstream>
15 #include <time.h>
16 #define x first
17 #define y second
18 #define pb push_back
19 #define mp make_pair
20 #define lson l,m,rt*2
21 #define rson m+1,r,rt*2+1
22 #define mt(A,B) memset(A,B,sizeof(A))
23 using namespace std;
24 typedef long long LL;
25 const double PI = acos(-1);
26 const int N=100;
27 const LL mod=1e9+7;
28 const int inf = 0x3f3f3f3f;
29 const LL INF=0x3f3f3f3f3f3f3f3fLL;
30 LL n,b,k,x,p;
31 LL num[20];
32 struct Mat
33 {
34     LL mat[N][N];
35 }F,goal;
36 Mat operator * (Mat a,Mat b)
37 {
38     Mat c;
39     mt(c.mat,0);
40     for(int i=0; i<N; i++)
41     {
42         for(int j=0; j<N; j++)
43         {
44             for(int k=0; k<N; k++)
45             {
46                 c.mat[i][j]=(c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;
47             }
48         }
49     }
50     return c;
51 }
52 Mat pow_mod(Mat a,LL n)
53 {
54     Mat ans;
55     mt(ans.mat,0);
56     for(int i=0;i<N;i++)ans.mat[i][i]=1;
57     while(n)
58     {
59         if(n&1)ans=ans*a;
60         a=a*a;
61         n/=2;
62     }
63     return ans;
64 }
65 int main()
66 {
67 #ifdef Local
68     freopen("data.txt","r",stdin);
69 #endif
70     ios::sync_with_stdio(false);
71     cin.tie(0);
72     cin>>n>>b>>k>>x;
73     mt(num,0);
74     mt(F.mat,0);
75     mt(goal.mat,0);
76     for(int i=0; i<n; i++)
77     {
78         cin>>p;
79         num[p]++;
80     }
81     for(LL i=0; i<N; i++)
82     {
83         for(LL j=0; j<=9; j++)
84         {
85             LL w=((i*10)%x+j)%x;
86             F.mat[i][w]+=num[j];
87         }
88     }
89     for(LL i=0; i<=9; i++)
90     {
91         goal.mat[0][i%x]+=num[i];
92     }
93     goal=goal*pow_mod(F,b-1);
94     cout<<goal.mat[0][k]<<endl;
95 #ifdef Local
96     cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
97 #endif
98 }

View Code

Codeforces 621E—Wet Shark and Blocks（数位DP+矩阵快速幂优化）

相关推荐