【CodeForces 865G】Flowers and Chocolate / 题解

Origin

题目描述

Idea

待整理。。。

Code

#include
#define maxn 505
#define ll long long
using namespace std;
const int mo=1e9+7;
int n,m,a[maxn],b[maxn],c[maxn],z[maxn],A[maxn],B[maxn];
ll K;
void inc(int &x,int y){x=((x+y>=mo)?x+y-mo:x+y);}
void dec(int &x,int y){x=((x-y<0)?x-y+mo:x-y);}
void mult(int *u,int *v){
    int i,j;
    memset(z,0,sizeof(z));
    for(i=0;i<250;i++)
        for(j=0;j<250;j++)
            z[i+j]=(z[i+j]+1LL*u[i]*v[j])%mo;
    for(i=498;i>=250;i--)
        for(j=1;j<=m;j++)
            inc(z[i-b[j]],z[i]);
    for(i=0;i<250;i++) u[i]=z[i];
}
void fpm(int *c,ll n){
    memset(A,0,sizeof(A));
    A[0]=1;
    while(n){
        if(n&1) mult(A,c);
        n>>=1,mult(c,c);
    }
}
int main(){
    int i,j;
    scanf("%d %d %lld",&n,&m,&K);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=m;i++) scanf("%d",&b[i]);
    for(i=1;i<=n;i++){
        memset(c,0,sizeof(c));
        c[1]=1,fpm(c,a[i]);
        for(j=0;j<250;j++) inc(B[j],A[j]);
    }
    fpm(B,K);
    for(i=0;i<250;i++) B[i]=A[i];
    for(i=249;i>0;i--)
        for(j=1;j<=m;j++)
            if(i>=b[j]) inc(B[i-b[j]],B[i]);
    cout<