搬自洛谷的一道题,可能起一个防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,有需要的大佬可以提前了解,已经掌握的大佬请无视蒟蒻颤抖。
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.