2 条题解

  • 0
    @ 2025-10-8 16:56:45
    #include<stdio.h>
    #include<string.h>
    int dp[11][91][91][91];
    int a[11],len;
    int dfs(int dep,int sum,int num,int mod,bool lim){
    	if(!dep)return sum==mod&&!num;
    	if(!lim&&~dp[dep][sum][num][mod])return dp[dep][sum][num][mod];
    	int res=0;
    	const int up=lim?a[dep]:9;
    	for(int i=0;i<=up;++i)
    		if(sum+i<=mod)res+=dfs(dep-1,sum+i,((num<<3)+(num<<1)+i)%mod,mod,lim&(i==a[dep]));
    	if(!lim)dp[dep][sum][num][mod]=res;
    	return res;
    }
    inline int solve(int n){
    	len=0;
    	for(int i=n;i;i/=10)a[++len]=i%10;
    	int res=0;
    	for(int i=9*len;i;--i)
    		res+=dfs(len,0,0,i,1);
    	return res;
    }
    int l,r;
    int main(){
    	memset(dp,-1,sizeof(dp));
    	while(~scanf("%d%d",&l,&r))
    		printf("%d\n",solve(r)-solve(l-1));
    	return 0;
    }
    
    • 0
      @ 2025-10-8 16:56:36
      #include<stdio.h>
      #include<string.h>
      int dp[11][91][91][91];
      int a[11],len;
      int dfs(int dep,int sum,int num,int mod,bool lim){
      	if(!dep)return sum==mod&&!num;
      	if(!lim&&~dp[dep][sum][num][mod])return dp[dep][sum][num][mod];
      	int res=0;
      	const int up=lim?a[dep]:9;
      	for(int i=0;i<=up;++i)
      		if(sum+i<=mod)res+=dfs(dep-1,sum+i,((num<<3)+(num<<1)+i)%mod,mod,lim&(i==a[dep]));
      	if(!lim)dp[dep][sum][num][mod]=res;
      	return res;
      }
      inline int solve(int n){
      	len=0;
      	for(int i=n;i;i/=10)a[++len]=i%10;
      	int res=0;
      	for(int i=9*len;i;--i)
      		res+=dfs(len,0,0,i,1);
      	return res;
      }
      int l,r;
      int main(){
      	memset(dp,-1,sizeof(dp));
      	while(~scanf("%d%d",&l,&r))
      		printf("%d\n",solve(r)-solve(l-1));
      	return 0;
      }
      
      • 1

      0x50 动态规划(0x5D 数位统计DP)例题2:月之谜

      信息

      ID
      1397
      时间
      1000ms
      内存
      512MiB
      难度
      6
      标签
      递交数
      65
      已通过
      18
      上传者