AHOI2009 同类分布

wjh15101051's space

卧薪尝胆，厚积薄发。

AHOI2009 同类分布

Date: Tue May 29 19:50:24 CST 2018

In Category: NoCategory

Description:

求出 $[L,R]$ 中各位数字之和能整除原数的数的个数。

$1\le L \le R \le 10^{18}$

Solution:

$f[i][j][k]$ 表示 $i$ 位，各位数字之和为 $j$ ，对 $m$ 取模余数是 $k$ 的数的个数，在外层枚举 $m$ 就行了。

Code:


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll l,r;

#define MAXL 21

int bit[MAXL];

ll f[MAXL][10 * MAXL][10 * MAXL];

int len = 0;

ll dfs(int pos,int sum,int mod,int rem,bool bord)

{

	if(pos == 0)

	{

		if(sum == mod && rem == 0)return 1;

		else return 0;

	}

	if(!bord && f[pos][sum][rem] != -1)return f[pos][sum][rem];

	int limit = (bord ? bit[pos] : 9);

	ll res = 0;

	for(int i = 0;i <= limit;++i)

	{

		res += dfs(pos - 1,sum + i,mod,(rem * 10 + i) % mod,(bord && (i == limit)));

	}

	if(!bord)f[pos][sum][rem] = res;

	return res;

}

ll calc(ll t)

{

	len = 0;

	memset(bit,0,sizeof(bit));

	while(t > 0)

	{

		bit[++len] = t % 10;

		t /= 10;

	}

	ll res = 0;

	for(int m = 1;m <= 9 * len;++m)

	{

		memset(f,-1,sizeof(f));

		res += dfs(len,0,m,0,true);

	}

	return res;

}

int main()

{

	cin >> l >> r;

	cout << calc(r) - calc(l - 1) << endl;

	return 0;

}

In tag: DP-数位DP

wjh15101051