126、十六夜咲夜的题目.docx

解题思路

本题考查的是?数位DP?思想。

数位?是指把一个数字按照?个、十、百、千?等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是?0～9，其他进制可类比十进制。

数位DP?：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）；

这些条件经过转化后可以使用「数位」的思想去理解和判断；

输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；

上界很大（比如?10^12），暴力枚举验证会超时。

数位DP?的基本原理：

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从?7000?数到?7999、从?8000?数到?8999、和从?9000?数到?9999?的过程非常相似，它们都是后三位从000?变到?999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用?递推?或?DP?的方式进行状态转移。

数位DP?中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减ans[l,r]=ans[0,r]?ans[0,l?1]。

那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化有哪些信誉好的足球投注网站，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

我们从代码角度来理解?数位DP。

一般来说?数位DP?用记忆化有哪些信誉好的足球投注网站更容易编写。

intdfs(intpos,intsta,boolf1,boollead)

{

intcnt=popcount(sta);

if(pos==-1)returncnt==k!lead;

if(cntk)return0;

if(!f1dp[pos][cnt][lead]!=-1)returndp[pos][cnt][lead];

intup=f1?a[pos]:15,res=0;

for(inti=0;i=up;i++)

res=(res+dfs(pos-1,(!ilead)?sta:sta|(1i),f1i==up,lead!i))%mod;

return!f1?dp[pos][cnt][lead]=res:res;

}

popcount?是用来统计数字中?11?的数量，记忆化数组?dp_{i,j,k}dpi,j,k?设计成当前遍历到第?ii?位有?jj?个?11?且没有前导?00?符合题目要求的数字数量。

dfs?函数的参数分别是以下含义：

pos?：用来计算一共选了第几位。

std?：用一个?1010?进制数加位运算或统计当前用了几个?1616?进制数。

f1?：用来看是否有上界限制。

lead：用来看是否有前导?00。

intcnt=popcount(sta);

if(pos==-1)returncnt==k!lead;

if(cntk)return0;

if(!f1dp[pos][cnt][lead]!=-1)returndp[pos][cnt][lead];

前面这段部分就是?数位DP?正常的记忆化流程。

intup=f1?a[pos]:15,res=0;

该代码用于判断当前枚举位置上界。

for(inti=0;i=up;i++)

res=(res+dfs(pos-1,(!ilead)?sta:sta|(1i),f1i==up,lead!i))%mod;

return!f1?dp[pos][cnt][lead]=res:res;

以上代码用于枚举下一位，这里需要注意?sta|(1i)?是用来标记已经选了几个?1616?进制数。

综上，即可完成?数位DP?的记忆化有哪些信誉好的足球投注网站部分。

AC_Code

C++

#includeiostream

#includecstdio

#includecstring

#includealgorithm

#includecmath

#includevector

#includeset

#includemap

#includestack

#includequeue

#definelllonglong

#defineinf0x3f3f3f3f

#defineintll

#defineendl\n

#defineIOSio