2015
04-14

# Zero’s Number

Xnozero is very interested in k-divide number.

A way of k-divide on a number is defined as if number N can be divide into two parts m, n, and the sum of m and n can be divided by k, then this is a way of k-divide number based k.

For example, 3 + 33 = 36 is a way of 3-divide on number 333, as you can only divide 333 into 3 and 33, and the sum of 3 and 33 is 36, which can be divided by 3.

Zero’s number is defined as f(n,k), and f(n,k) is the number of ways of n divided into k-divide numbers.

As defined above, 333 can be divided into two parts in two ways 3|33 and 33|3, so f(333,3)=2.

Now give you A, B, K, can you help Xnozero compute the sum of f(i,K) (A≤i≤B)? (1 ≤ K ≤ 20, 10 ≤ A ≤ B ≤ 1017)

Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.

Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.

333 333 3
10 100 2

2
46

dp[22][22][22][22][2]，   代表 i位，分点为fd，余数mod，对于k取余，是否有前导零

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"stack"
#include"algorithm"
#include"iostream"
using namespace std;
__int64 dp[22][22][22][22][2],ten[22];  //i位，分点为fd，余数mod，对于k取余，是否有前导零
int num[22],cnt;
__int64 dfs(int site,int fd,int mod,int k,int ff,int f)
{
if(site==0)  return mod?0:1;
if(!f&&dp[site][fd][mod][k][ff]!=-1) return dp[site][fd][mod][k][ff];
int len=f?num[site]:9;
__int64 ans=0;
for(int i=0; i<=len; i++)
{
if(site>fd)
{
if(ff==0&&site==fd+1&&i==0) continue; //前导0不能到分点前，也就是前半部分不能为0
ans+=dfs(site-1,fd,(i*ten[site-fd]+mod)%k,k,ff||i!=0,f&&i==len);
}
else
ans+=dfs(site-1,fd,(i*ten[site]+mod)%k,k,ff||i!=0,f&&i==len);
}
if(!f) dp[site][fd][mod][k][ff]=ans;
return ans;
}
__int64 solve(__int64 x,int k)
{
cnt=0;
if(x<10) return 0;
__int64 ans=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
for(int i=1; i<cnt; i++)  //枚举分点 分界为这位之后
ans+=dfs(cnt,i,0,k,0,1);
return ans;
}
int main()
{
__int64 a,b;
int k;
memset(dp,-1,sizeof(dp));
ten[1]=1;
for(int i=2; i<=18; i++) ten[i]=ten[i-1]*10;
while(scanf("%I64d%I64d%d",&a,&b,&k)!=-1)
{
printf("%I64d\n",solve(b,k)-solve(a-1,k));
}
return 0;
}


1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

2. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示

3. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}