1 solutions

  • 0
    @ 2023-2-7 15:04:36

    搬自洛谷的一道题,可能起一个防AK的作用,虽然可能没起到就是了

    #include<cstdio>
    #include<cstring>
    using namespace std;
    int dp[10001][10][10],a[1000],p[1000],r[100],t[10][10][10],cnt=0,cnt2=0,i,c,d,e,j,ans,n;
    void premanage()
    {
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        memset(r,0,sizeof(r));
        memset(t,0,sizeof(t));
        memset(dp,0,sizeof(dp));
        for(i=2;i<1000;i++)
        {
            if(!a[i])
            {
                if(i<100)p[++cnt]=i;
                else
                {
                    c=i/10%10;d=i%10;e=i/100;
                    dp[3][c][d]++;
                    if(!t[c][d][0])r[++cnt2]=i%100;
                    t[c][d][0]++;
                    t[c][d][t[c][d][0]]=e;
                }
            }
            for(j=1;j<=cnt&&i*p[j]<1000;j++)a[i*p[j]]=1;
        }
    }
    int dpp(int n,int c,int d)
    {
        int i;
        if(n<3)return 0;
        if(!dp[n][c][d])for(i=1;i<=t[c][d][0];i++)dp[n][c][d]=(dp[n][c][d]+dpp(n-1,t[c][d][i],c))%1000000009;
        return dp[n][c][d];
    }
    void solve()
    {
    for(i=1;i<=cnt2;i++)ans=(ans+dpp(n,r[i]/10,r[i]%10))%1000000009;
    }
    int main()
    {
        scanf("%d",&n);
        premanage();
        solve();
        printf("%d",ans);
        return 0;    
    }
    

    贴一个大佬的代码,大家也可以移步洛谷该题,实际是一道dp,有需要的大佬可以提前了解,已经掌握的大佬请无视蒟蒻颤抖

    • 1

    Information

    ID
    6689
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    8
    Tags
    # Submissions
    5
    Accepted
    3
    Uploaded By