Description

给定$n$个数和$b$个盒子,放一些数到盒子中,使得盒子不为空。每个盒子中的数是一样的,一个数可以被放到多个盒子中。

从每个盒子中取一个数,组成一个$b$位数,如果这个数$mod\;k=x$,则这是一种合法的方案。求方案数$mod\;10^9+7$。

Input

第一行为$4$个数$n,b,x,k$。

Output

一行,表示方案数$mod 10^9+7$。

Sample Input

3 2 1 2
3 1 2

Sample Output

6

HINT

$2\;\leq\;n\;\leq\;50000,1\;\leq\;b\;\leq\;10^9,0\;\leq\;k\;\leq\;100, x\;\geq\;2,1\;\leq\;a_i\;\leq\;9$

Solution

显然序列中有用的条件仅有每个数出现的次数,记为$t[\;]$。

$f[i][j]$表示前$i$位数$mod\;k$的值为$j$的方案数。

$f[i+1][(j\;\times\;10+l)mod\;n]=f[i][j]\;\times\;t[l]$。

矩乘优化$DP$就能过了。

 #include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define lld I64d
#define K 15
#define N 105
#define M 1000000007
using namespace std;
typedef long long ll;
struct matrix{
ll a[N][N];int n,m;
}a,b;
ll t[K];
int n,m,k,x;
inline matrix mult(matrix a,matrix b){
matrix c;c.n=a.n;c.m=b.m;
for(int i=;i<c.n;++i)
for(int j=;j<c.m;++j){
c.a[i][j]=;
for(int k=;k<a.m;++k)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%M;
}
return c;
}
inline matrix po(matrix a,int k){
matrix c;c.n=a.n;c.m=a.m;
for(int i=;i<a.n;++i)
for(int j=;j<b.n;++j)
if(i!=j) c.a[i][j]=;
else c.a[i][j]=;
while(k){
if(k&) c=mult(c,a);
a=mult(a,a);k>>=;
}
return c;
}
inline void init(){
scanf("%d%d%d%d",&n,&m,&x,&k);
for(int i=,j;i<=n;++i){
scanf("%d",&j);++t[j];
}
a.n=k;a.m=;
for(int i=;i<=;++i)
a.a[i%k][]+=t[i];
b.n=b.m=k;
for(int i=,l;i<k;++i){
for(int j=;j<=;++j){
l=(i*+j)%k;
b.a[l][i]+=t[j];
}
}
matrix c=mult(po(b,m-),a);
printf("%lld\n",c.a[x][]);
}
int main(){
freopen("blocks.in","r",stdin);
freopen("blocks.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}

最新文章

  1. sdut 2163:Identifiers(第二届山东省省赛原题,水题)
  2. SqlSever基础 union 联合查询,厉害的并集 重复项只显示一个 两个查询结果并在一起后排序
  3. jQuery选择器之动态列表显示Demo
  4. 转:六百字读懂Git
  5. React-Native之ViewPagerAndroid的使用
  6. 导航栏控制器和标签栏控制器(UINavigationController和UITabBarController)混用
  7. 字节转换/编码转换全为转载GBK,BIG5,utf8,unicode
  8. mybatis判断list为空
  9. Scikit-learn:模型评估Model evaluation
  10. 读《图解HTTP》有感-(确保WEB安全的HTTPS)
  11. app自动化测试之实战应用(百度app简单测试)
  12. 【Big Data - Hadoop - MapReduce】初学Hadoop之图解MapReduce与WordCount示例分析
  13. System.ServiceProcess.TimeoutException: Time out has expired and the operation has not been completed.
  14. kafka中的消费组
  15. STL概论
  16. [工具]Sublime 显示韩文
  17. windows结束端口对应的进程
  18. 对话框上动态控件的创建、在Picture Control控件上显示图片
  19. Page与Loaded
  20. numpy基本方法总结 --good

热门文章

  1. October 29th Week 44th Saturday 2016
  2. UNET学习笔记2 - 高级API(HLAPI)
  3. windows无法安装到这个磁盘怎样解决
  4. Yii2.0 GridView 新增添加按钮
  5. python学习之路-day3
  6. Invalid Image Path - No image found at the path referenced under key &quot;CFBundleIconFile&quot;: Icon.png
  7. Mindjet MindManager 2016/2017 折腾记录
  8. java poi导出EXCEL xls文件代码
  9. spring boot 1.4默认使用 hibernate validator
  10. 【HDOJ】1494 跑跑卡丁车
  11. 内核级HOOK的几种实现与应用
  12. 用C++写一个简单的服务器和客户端
  13. Windows平台Go调用DLL的坑(居然有这么多没听过的名词)
  14. 白夜追凶 :手 Q 图片的显示和发送逻辑
  15. 【机器学习实战】第 10 章 K-Means(K-均值)聚类算法
  16. sql sever insert into混合嵌套插入
  17. Python二级-----------程序冲刺3
  18. 2018-2019-2 网络对抗技术 20165206 Exp6 信息搜集与漏洞扫描
  19. SharePoint Framework 在web部件中使用已存在的JavaScript库 - 捆绑打包和外部引用
  20. mysql数据库的优化和查询效率的优化