首页 > 代码库 > [蒟蒻修炼计划][cf621E]Wet Shark and Blocks
[蒟蒻修炼计划][cf621E]Wet Shark and Blocks
Description
给定n个数和b个盒子，放一些数到盒子中，使得盒子不为空。每个盒子中的数是一样的，一个数可以被放到多个盒子中。
从每个盒子中取一个数，组成一个b位数，如果这个数mod k=x，则这是一种合法的方案。求方案数mod 109+7。
Input
第一行为4个数n,b,x,k。
Output
一行，表示方案数mod 109+7。
Sample Input
3 2 1 2
3 1 2
Sample Output
6
HINT
2<=n<=50000, 1<=b<=109, 0<=k <x<=100, x>=2,1<=ai<=9
Solution
显然序列中有用的条件仅有每个数出现的次数，记为t[]。
f[i][j]表示前i位数mod k的值为j的方案数。
f[i+1][(j*10+l)mod n]=f[i][j]*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 1000000007using 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=0;i<c.n;++i) for(int j=0;j<c.m;++j){ c.a[i][j]=0; for(int k=0;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=0;i<a.n;++i) for(int j=0;j<b.n;++j) if(i!=j) c.a[i][j]=0; else c.a[i][j]=1; while(k){ if(k&1) c=mult(c,a); a=mult(a,a);k>>=1; } return c;}inline void init(){ scanf("%d%d%d%d",&n,&m,&x,&k); for(int i=1,j;i<=n;++i){ scanf("%d",&j);++t[j]; } a.n=k;a.m=1; for(int i=1;i<=9;++i) a.a[i%k][0]+=t[i]; b.n=b.m=k; for(int i=0,l;i<k;++i){ for(int j=1;j<=9;++j){ l=(i*10+j)%k; b.a[l][i]+=t[j]; } } matrix c=mult(po(b,m-1),a); printf("%lld\n",c.a[x][0]);}int main(){ freopen("blocks.in","r",stdin); freopen("blocks.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0;}
[蒟蒻修炼计划][cf621E]Wet Shark and Blocks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。