codeforces #341 div 2 E. Wet Shark and Blocks (数位dp+矩阵加速)

2016-02-08 · 2 min read · dp 快速幂数位dp 矩阵

http://codeforces.com/problemset/problem/621/E

题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。

思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。

但是由于b很大（1E9）,所以需要用矩阵加速。

/* ***********************************************
Author :111qqz
Created Time :2016年02月08日 星期一 16时24分34秒
File Name :code/cf/#341/E.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const LL MOD=1E9+7;
 7int n,b,k,X;
 8struct Matrix
 9{
10    LL a[110][110];

};

 1void add(LL &x,LL y)
 2{
 3    x += y;
 4    x %= MOD;
 5}
 6Matrix multi(Matrix x,Matrix y )   //矩阵乘法。
 7{
 8    Matrix z;
 9    ms(z.a,0LL);
10    for ( int i =  0 ; i < X  ;i++)
11    {
12    for ( int k = 0 ; k < X ; k++)
13    {
14        if (x.a[i][k]==0) continue;
15        for ( int j = 0 ; j < X ; j++)
16        add(z.a[i][j],x.a[i][k]*y.a[k][j]);

1    }
2    }
3    return z;
4}

 1Matrix Pow(Matrix x,int n)  //矩阵快速幂
 2{
 3    Matrix y;
 4    ms(y.a,0LL);
 5    for ( int i = 0 ; i < X ; i++) y.a[i][i] = 1LL;
 6    while (n)
 7    {
 8    if (n&1)
 9        y = multi(x,y);
10    x = multi(x,x);
11    n >>=1;
12    }
13    return y;
14}

1int cnt[20];
2int main()
3{
4    #ifndef  ONLINE_JUDGE 
5    freopen("code/in.txt","r",stdin);
6  #endif

    cin>>n>>b>>k>>X;

1    Matrix ori,res;
2    ms(ori.a,0LL);
3    ms(cnt,0);
4    for ( int i = 1 ; i <= n ; i++)
5    {
6        int tmp;
7        scanf("%d",&tmp);
8        cnt[tmp]++;
9    }

1    for ( int i = 0 ; i < X ; i++)
2        for (int j = 0 ; j <= 9 ; j++)
3        add(ori.a[i][(i*10+j)%X],1LL*cnt[j]);
4    res = Pow(ori,b);
5    cout<<res.a[0][k]<<endl;

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}