[BZOJ5064]B-number

题目大意：

求\(1\sim n(n\le10^{15})\)间有多少数满足是\(13\)的倍数且包含字符串\(13\)。

思路：

数位DP。\(f[i][j][k]\)表示考虑\(i\)位，模\(13\)余数是\(j\)，上一位数字是\(k\)时的方案数。

源代码：

#include<cstdio>

#include<cctype>

#include<utility>

#include<cstring>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

int d[16];

int64 pwr[16];

typedef std::pair<int64,int64> Node;

Node f[16][13][10];

Node dp(const int &dep,const bool &zero,const bool &limit,const int &r,const int &last) {

	if(dep==0) return std::make_pair(!zero&&!r,0);

	const int lim=limit?d[dep]:9;

	if(!zero&&!limit&&f[dep][r][last]!=(Node){-1,-1}) return f[dep][r][last];

	Node ret=std::make_pair(0,0);

	for(register int i=0;i<=lim;i++) {

		const Node p=dp(dep-1,zero&&!i,limit&&i==lim,(r+i*pwr[dep])%13,i);

		if(last==1&&i==3) {

			ret.second+=p.first;

		} else {

			ret.first+=p.first;

		}

		ret.second+=p.second;

	}

	if(!zero&&!limit) f[dep][r][last]=ret;

	return ret;

}

inline int64 solve(int64 x) {

	for(;x;x/=10) {

		d[++d[0]]=x%10;

		pwr[d[0]]=d[0]==1?1:pwr[d[0]-1]*10%13;

	}

	return dp(d[0],true,true,0,0).second;

}

int main() {

	memset(f,-1,sizeof f);

	const int64 n=getint();

	printf("%lld\n",solve(n));

	return 0;

}

巴特西

[BZOJ5064]B-number

[BZOJ5064]B-number

题目大意：

思路：

源代码：

最新文章

热门文章