zcmimi's blog

查看原题

点击跳转

很容易想出普通的dp

不过n \le 10^{18},所以要构造加速矩阵,使用矩阵快速幂

#include<bits/stdc++.h>
const int N=111,P=1000000007,m=100;
struct mat{
    int a[N][N];
    mat operator*(const mat&x)const{
        mat c;memset(c.a,0,sizeof c.a);
        for(int k=1;k<=m;++k)
            for(int i=1;i<=m;++i)
                for(int j=1;j<=m;++j)
                    (c.a[i][j]+=1ll*a[i][k]*x.a[k][j]%P)%=P;
        return c;
    }
}A,B;
std::bitset<N>a,b;
int main(){
    long long n;int t,x;
    scanf("%lld",&n);
    for(scanf("%d",&t);t--;)scanf("%d",&x),a[x]=1;
    for(scanf("%d",&t);t--;)scanf("%d",&x),b[x]=1;
    a&=b;
    A.a[1][m]=1;
    for(int i=1;i<m;++i)B.a[i+1][i]=1;// f[i] -> f[i+1]
    for(int i=1;i<=m;++i)
        if(a[i])B.a[m-i+1][m]=1;// f[m]+=f[m-i+1]
    for(;n;n>>=1,B=B*B)if(n&1)A=A*B;
    printf("%d\n",A.a[1][m]);
}
LG 5343 【XR-1】分块
comment评论
Search
search