P9640 [SNCPC2019] Digit Mode
思路：界说 \(F(l,r)\) 表现若已经确定了 \(\) 的数，且 \(\) 没有限制的贡献数。
设 \(n\) 的长度为 \(len\)，考虑先求出 \((i \le len-1)\) 的贡献（是没有限制的），那么每次枚举第 \(1\) 位数字 \(a_1 \in \)，算上 \(F(2,i)\) 的贡献即可。
则该情况贡献和为：
\[\sum_{i=1}^{len-1} \sum_{j=1}^9 F(2,i)\]
现在来考虑长度为 \(len\) 的数的贡献的和，也考虑枚举第 \(i\) 位的数字 \(j\)，那么若想要使得 \(\) 没有限制，则至少要满足 \(i \in \)，为了使得后面不算重，故我们要每次算完 \(\) 的贡献和后，需要令 \(a_i = n_i\)。
则该情况贡献和为：
\[\sum_{i=1}^{len} \sum_{j=}^{n_i-1} F(i+1,len)\]
留意最后要单独计算 \(n\) 本身的贡献。
现在我们来考虑确定 \(a_{1,\cdots,l-1}\) 的情况下如何计算 \(F(l,r)\)。
考虑枚举众数最大值 \(i\) 和众数的出现次数 \(j\)，设 \(p_i\) 表现 \(i\) 的出现次数，那么在后面 \(\) 内 \(i\) 至少还需要出现 \(j-p_i\) 次；同时为了确保 \(i\) 是众数，需要满足 \(\) 的出现次数 \(\le j\)，且 \(\) 的出现次数 \(\le j-1\)；即现在我们要求将 \(r-l+1-(j-p_i)\) 个位置分配给除了 \(i\) 以外的 \(9\) 个数的且满足限制的方案数。
设我们枚举的众数为 \(k\)，众数出现次数为 \(mx\)，利用动态规划算法，界说 \(f_i\) 表现可以分配 \(i\) 个位置的方案数，考虑枚举选的数 \(j\) 和分配给 \(j\) 的数量 \(k\)，背包形转移：
\ \sum_{k=0}^{\min(mx,p_j-)} \binom{i}{k} f_{i-k}\]
可以先预处理阶乘和逆元来计算组合数。
留意要先枚举 \(j\)。
完整代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=55,mod=1e9+7;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c
页:
[1]