数位dp求调,不明白思路哪里出问题
查看原帖
数位dp求调,不明白思路哪里出问题
305895
Take_A_Single_6楼主2023/10/28 23:59
#include<bits/stdc++.h>
#define maxn 1000005
#define inf 2147483647
#define mod 1000000007
#define int long long
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX% 10 + '0');
}
int n,K,m,f[1005][15][105],b[15],s1,s2;
signed main()
{
	n=read(),K=read(),m=read(),f[0][0][0]=1;
	for(int i=0;i<10;i++)f[1][i][i%K]=(f[1][i][i%K]+1)%m,b[i]=i%K;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<10;j++)b[j]=b[j]*10%K;
		for(int j=0;j<10;j++)
			for(int k=0;k<K;k++)
				for(int p=0;p<10;p++)
					f[i][j][k]+=f[i-1][p][((k-b[j])%K+K)%K],f[i][j][k]%=m;
	}
	for(int i=0;i<10;i++)s1=(s1+f[n][i][0])%m,s2=(s2+f[n-1][i][0])%m;
	write(((s1-s2)%m+m)%m);
	return 0;
}

rt,想按板子的写法,但是第三个样例就过不了

2023/10/28 23:59
加载中...