题解-Roman and Numbers

前置知识：

数位 \(\texttt{dp}\) </>

\(\color{#9933cc}{\texttt{Roman and Numbers}}\)

给定 \(n\) 和 \(m\)，求将 \(n\) 的各位数字重新排列（不允许有前导 \(0\)），求可以构造几个能被 \(m\) 整除。

数据范围：\(1\le n\le 10^{18}\)，\(1\le m\le 100\)。

用数位 \(\texttt{dp}\) 代码又短时间又优又好理解，为什么没人玩呢？

把 \(n\) 的各位数字拿出来排序一下，然后把每个数有没有用过状压。

for(;n;n/=10) d.pb(n%10);

sort(d.begin(),d.end()),len=d.size();

选数字的时候只允许用相同数字中第一个没用过的。

\(\texttt{Dfs}\) 中：

\(w\)：要找从右往左第几位。
\(st\)：当前数字使用状态。
\(sum\)：左 \(len-w\) 位数字形成的数 \(\bmod m\) 的余数。

il lng Dfs(re int w,re int st,re int sum){

	if(!w) return sum==0;//判断被 m 整除

	if(~f[st][sum]) return f[st][sum];

	re lng res=0;

	for(re int i=0;i<len;i++)

		if(!((1<<i)&st)&&(i==0||d[i]!=d[i-1]||((1<<(i-1))&st))) //*

			res+=Dfs(w-1,st|(1<<i),(sum*10+d[i])%m);

	return f[st][sum]=res; //记忆化，记录答案

}

其中 \(*\) 处的判断：

该数字未用过。
该数字前的相同数字都用过。

以保证使用顺序，防止重复统计。

关于 \(f\) 记忆化数组：

现在是 \(f_{st,sum}\)，本来应该是 \(f_{w,st,sum}\)。这里就讲讲 \(f_{w,st,sum}\) 记忆化的缺点：

\(1\le w\le 18\)，\(1\le st\le 2^{18}\)，\(1\le sum<m\le 100\)，必然 \(\color{#117}{\texttt{MLE}}\)。
\(st\) 中 \(1\) 的数量 \(cnt\) 必然满足 \(cnt=len-w\)，所以只记录 \(st\) 不会重合答案。

时间复杂度 \(\Theta(2^{len}m)\)。

Code

#include <bits/stdc++.h>

using namespace std;

//&Start

#define re register

#define il inline

#define mk make_pair

#define pb push_back

#define db double

#define lng long long

#define fi first

#define se second

#define inf 0x3f3f3f3f

//&Data

const int W=18,M=100;

int m,len;

lng n,f[1<<W|7][M|7];

vector<int> d;

//&Digitdp

il void Pre(){memset(f,-1,sizeof f);}

il lng Dfs(re int w,re int st,re int sum){

	if(!w) return sum==0;

	if(~f[st][sum]) return f[st][sum];

	re lng res=0;

	for(re int i=0;i<len;i++)

		if(!((1<<i)&st)&&(i==0||d[i]!=d[i-1]||((1<<(i-1))&st)))

			res+=Dfs(w-1,st|(1<<i),(sum*10+d[i])%m);

	return f[st][sum]=res;

}

il lng DP(){

	for(;n;n/=10) d.pb(n%10);

	sort(d.begin(),d.end()),len=d.size();

	re lng res=0;

	for(re int i=0;i<len;i++)

		if(d[i]&&(i==0||d[i]!=d[i-1])) // 这里也要判断！这是最容易错的地方

			res+=Dfs(len-1,1<<i,d[i]%m);

	return res;

}

//&Main

int main(){

	scanf("%lld%d",&n,&m),Pre();

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

	return 0;

}

祝大家学习愉快！

巴特西

题解-Roman and Numbers

题解-Roman and Numbers

Code

最新文章

热门文章