CF514E 题解（极简版）

__vector__ · 2022-08-12 11:54:12 · 个人记录

做法

可以快速得出 x \in [1,100] 的答案。
将其记录下来，通过矩阵乘法转移到 x \in [2,101] 的答案。
以此类推。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const ll mod=1e9+7;
    const int maxn=1e5+5;
    const int mamx=105;
    int n,x,d[maxn];
    struct Matrix
    {
        ll imap[mamx][mamx];
        void init()
        {
            memset(imap,0,sizeof imap);
        }
        Matrix operator*(const Matrix& b)
        {
            Matrix ans;
            ans.init();
            for(int i=1;i<=101;i++)
            {
                for(int j=1;j<=101;j++)
                {
                    for(int k=1;k<=101;k++)
                    {
                        ans.imap[i][j]+=imap[i][k]*b.imap[k][j];
                        ans.imap[i][j]%=mod;
                    }
                }
            }
            return ans;
        }
    }A,B,out;
    Matrix ksm(Matrix a,ll b)
    {
        Matrix ret;
        ret.init();
        for(int i=1;i<=101;i++)ret.imap[i][i]=1;
        while(b)
        {
            if(b&1)ret=ret*a;
            a=a*a;
            b>>=1;
        }
        return ret;
    }
    ll f0[105],f[105],cnt[105];
    void main()
    {
        scanf("%d%d",&n,&x);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&d[i]);
            cnt[d[i]]++;
        }
        f0[0]=1;
        for(int i=1;i<=100;i++)
        {
            for(int j=1;j<=i;j++)
            {
                f0[i]+=cnt[j]*f0[i-j];
                f0[i]%=mod;
            }
        }
        f[0]=1;
        for(int i=1;i<=100;i++)
        {
            f[i]=f[i-1]+f0[i];
            f[i]%=mod;
        }
        if(x<=100)
        {
            printf("%lld",f[x]);
            return;
        }
        A.init();
        B.init();
        for(int i=1;i<=101;i++)
        {
            A.imap[1][i]=f[100-i+1];
        }
        for(int i=1;i<=100;i++)
        {
            B.imap[i][1]=cnt[i];
        }
        B.imap[101][1]=1;//根节点没选，选上
        for(int i=1;i<=99;i++)
        {
            B.imap[i][i+1]=1;
         } 
        B.imap[101][101]=1;
        out=A*ksm(B,x-100);
        printf("%lld",out.imap[1][1]);
    }
}
int main()
{
    Main::main();
    return 0;
}