CF621E-Wet Shark and Blocks

CF621E-Wet Shark and Blocks

题目大意

你现在一共有b bb堆一模一样的数字，每堆数字中有n nn个1 − 9 1-91−9的一位数。你现在可以从每一堆里恰好选一个数，将这些数从左到右拼成一个大数。将这个拼成的大数对x xx取模，问你最后结果是k kk的取法有多少，取法数量对1 e 9 + 7 1e9+71e9+7取模。

题解

可以发现，设d p [ m ] [ i ] dp[m][i]dp[m][i]为前m mm堆余数为i ii的种数，有如下递推式d p [ m + 1 ] [ ( i ∗ 10 + v a l ) % x ] + = d p [ m ] [ i ] dp[m+1][(i*10+val) \% x]+=dp[m][i]dp[m+1][(i∗10+val)%x]+=dp[m][i]，v a l valval为下一堆中取的数字。可以发现递推式只和相邻两堆有关。所以可以简化成d p [ i ] [ ( i ∗ 10 + v a l ) % x ] = Σ i [ n u m [ i ] = = v a l ] dp[i][(i*10+val) \% x]=\Sigma_i [num[i]==val]dp[i][(i∗10+val)%x]=Σi​[num[i]==val]，表示从余数i ii转移到下一堆余数( i ∗ 10 + v a l ) % x (i*10+val) \% x(i∗10+val)%x的种数。接下来就是对这个矩阵进行矩阵快速幂加速得到结果。

#include<bits/stdc++.h>#defineiosios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'usingnamespacestd;#defineintlonglongconstintmod=1e9+7;structMatrix{intn,m;vector<vector<int>>a;Matrix(int_n=0,int_m=0):n(_n),m(_m){a.resize(n,vector<int>(m,0));}Matrixoperator*(constMatrix&b)const{if(m!=b.n)throw"Matrix dimension error";Matrixres(n,b.m);for(inti=0;i<n;i++){for(intj=0;j<b.m;j++){for(intk=0;k<m;k++){res.a[i][j]=(res.a[i][j]+1LL*a[i][k]*b.a[k][j])%mod;}}}returnres;}Matrixpow(longlongk)const{if(n!=m)throw"Matrix must be square";Matrixres(n,n),base=*this;for(inti=0;i<n;i++)res.a[i][i]=1;while(k>0){if(k&1)res=res*base;base=base*base;k>>=1;}returnres;}};inlinevoidsolve(){intn,b,k,x;cin>>n>>b>>k>>x;MatrixA(x,x);for(inti=0;i<n;i++){intval;cin>>val;for(intj=0;j<x;j++){intnext=(j*10+val)%x;A.a[j][next]=(A.a[j][next]+1)%mod;}}Matrix Ab=A.pow(b);cout<<Ab.a[0][k]<<endl;}signedmain(){ios;intT=1;// cin >> T;while(T--)solve();return0;}