月之谜 (mystery.pas/c/cpp)
【题目描述】
打败了 Lord lsp 之后，由于 lqr 是一个心地善良的女孩子，她想净化 Lord lsp 黑化的心，使他变回到原来那个天然呆的 lsp……
在光之英雄 applepi 的指引下，lqr 来到了月之泉。月之泉的精灵告诉她，想要净化 Lord lsp 的话，就要解出月之泉的谜题。
具体地来说是这样的，定义月之数为能够被其十进制表示下各个数位的和整除的数。
给定整数 L,R，你需要计算出区间[L, R]中有多少个月之数。
lqr 发觉这不是数学竞赛能够解决的问题，于是她又找到了你……所以说你需要帮助她解决这个问题。
【输入格式】
输入文件包含多个测试数据。
每组测试数据占一行，含有两个整数 L 和 R。
输入文件以 EOF 结束。
【输出格式】
对于每组测试数据，在单独的一行内输出结果。
【样例输入】
1 100
101 200
【样例输出】
33
26
【数据范围与约定】
对于 20% 的数据，1≤L，R≤1000。
对于 100% 的数据，1≤L，R≤2 31 -1。
每个输入文件的测试数据不超过 3000 组。
——————————————我是分割线————————————————————
好题，数位统计DP
这就是著名的数位统计DP，首先把问题转化为calc(1,R)-calc(1,L-1)
一般解题思路是：先DP预处理、再从高到低按位填数
一旦填了一个比上限小的数位，就可以立即通过DP预处理出的值累加答案
f[模][剩余数字数目][剩余数字的和][剩余位的模]=合法方案数
f[S][i][j][k]=∑(f[S][i-1][j-R][(k-pwr[i-1]*R)%S], 0≤R≤9)
边界条件：F[S][0][0][0]=1
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iomanip>
#include<cassert>
#include<climits>
#define maxn 1000001
#define F(i,j,k) for(int i=j;i<=k;i++)
#define M(a,b) memset(a,b,sizeof(a))
#define FF(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x7fffffff
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m;
int f[][][][],pwr[][];;
int sum,L,R;
int num[];
inline int modabs (int a, int mod)
{
return ((a % mod)+mod)%mod;
}
int run(int p,int sum,int mod,int s,bool e)
{
int a,b;
if(s-sum<) return ;
else if(!e) return f[s][p+][s-sum][(s-mod)%s];
else if(p==-)
{
if(sum==s&&mod==) return ;
else return ;
}
else
{
int res=;
F(d,,num[p])
{
res+=run(p-,sum+d,(mod+pwr[s][p]*d)%s,s,d==num[p]);
}
return res;
}
}
int fcount(int t)
{
int a,b;
if(t==) return ;
int maxx=;
while(t){
num[maxx++]=t%;
t/=;
}
int res=;
F(i,,) res+=run(maxx-,,,i,true);
return res;
}
int main()
{
std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
F(s,,)
{
M(f[s],);
f[s][][][]=;
pwr[s][]=%s;
F(i,,) pwr[s][i]=(pwr[s][i-]*)%s;
F(i,,)F(j,,i*)F(k,,s)for(int d=;d<=&&j-d>=;d++)
{
f[s][i][j][k]+=f[s][i-][j-d][modabs(k-pwr[s][i-]*d,s)];
}
}
while(cin>>L>>R)
{
cout<<fcount(R)-fcount(L-)<<endl;
}
return ;
}
Nescafé2 月之谜