学习笔记 P2359 三素数数

tcswuzb · 2018-09-25 17:29:27 · 个人记录

题目描述

如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。

输入格式：

一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。

输出格式：

一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数

题意分析

由于n>=10000

所以直接枚举到(10^10000)是不行的

你数组也开不下

所以考虑使用专门的数位DP

设DP[n][j][k]表示当前位数为n时末两位为j,k的方案数

我们枚举后面可以相接的数x

当且仅当(100×j+10×k+x)是一个素数

这样的转移是合法的

以此进行DP

同时 为了防超时 使用欧拉线性筛预处理1000以内的素数

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define R register
#define IL inline
#define N 500008
#define mod 1000000009
#define int long long
using namespace std;
template<typename T>void read(T &A)
{
    T x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') f=0;ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    A=f ? x:-x;
}
bool mark[N<<1];
int prime[N<<1];
int n,tot;
int dp[10010][11][11];
IL void work()
{
    for(R int i=2;i<=(N<<1);++i)
    {
        if(!mark[i]) {prime[++tot]=i;}
        for(R int j=1;j<=tot;++j)
        {
            if(prime[j]*i>(N<<1)) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
signed main()
{
    read(n);
    work();
    for(R int i=1;i<=9;++i)
     for(R int j=1;j<=9;++j)
     {
         int tmp=0;
         for(R int k=1;k<=9;++k)
         if(!mark[k*100+10*i+j]) tmp++;
         dp[3][i][j]=tmp%mod;
     }
    for(R int i=4;i<=n;++i)
     for(R int j=1;j<=9;++j)
      for(R int k=1;k<=9;++k) 
       for(R int x=1;x<=9;++x)
        if(!mark[j*100+k*10+x])
         dp[i][k][x]=(dp[i][k][x]+dp[i-1][j][k])%mod;
    int ans=0;
    for(R int i=1;i<=9;++i)
     for(R int j=1;j<=9;++j)
      ans=(ans+dp[n][i][j])%mod;
    printf("%lld\n",ans);  
    return 0;
}

NOIP 2018 RP++