hdu2020多校3

发表于 分类于 ，

比赛链接

A. Tokitsukaze,CSL and Palindrome Game

链接

F. X Number

题意

将一个十进制数进行这样分类：

  • 统计每个数码的出现次数。

  • 如果出现次数有两个或以上的最大值，则分类为 $10$。

  • 否则，若数码 $d$ 的出现次数最多，则分类为 $d$。

多次询问，求 $[l,r]$ 内的数有多少个分类为 $d$。

$T\le 1000,d\in[0,9],1\le l \le r \le 10^{18}$，时限 $3s$。

题解

比赛时做法

一道非常显然的数位DP题。

在数位DP打破限制之后，相当于有 $10$ 个变量，此时为 $a_i$。最终为 $a’_i$，要求 $a’_d>a’_i(i\not=d)$。

此时可以在 $a$ 的基础上进行若干次将 $a_i+1$ 的操作，设这个次数为 $k$。

那么枚举 $a_d$ 加了 $j$ 次，然后算出将其他 $a_i$ 加 $k’=k-j$ 次后满足的条件的方案数，乘上系数 $\binom{k}{j}$ 即可。

这是对于所有的 $i\not =d$，你可以算出一个次数 $t_i$，表示第 $i$ 个数码最多只能加这么多次。

那么这个方案数就是 $k’![x^{k’}]\prod {d\not=i}(\sum{j=0}^{t_i}\frac{x^j}{j!})$

暴力卷积，时间复杂度 $O(18^2\times 9)$。

时间复杂度 $O(18^4\times 9\times 10 \times T)$，有若干小常数。

跑了大概3s+秒，然后神奇地将卷积数组改成了long double就跑得飞快。

优化

显然，18的拆分数是很小的，于是我们可以预处理最后的DP，这样就是正解了。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read()
{
	ll x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
int d;
ll c[20][20],fac[20];
long db f[20],g[20];
inline void init()
{
	fo(i,0,19)
	{
		c[i][0]=c[i][i]=1;
		fo(j,1,i-1)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	fac[0]=1;
	fo(i,1,18) fac[i]=fac[i-1]*i;
}
int st[20],top,s[20];
inline ll calc(int k,int v)
{
	if(!k) return 1;
	fo(i,0,18) f[i]=0;
	f[0]=fac[k];
	fd(j,9,0)
		if(j^d)
		{
			fo(x,0,k)
				fo(y,0,min(k-x,v-s[j]-1))
					g[x+y]+=f[x]/fac[y];
			fo(x,0,k) f[x]=g[x],g[x]=0;
		}
	return (ll)(f[k]);
}
inline ll work(int k)
{
	ll ans=0;
	int mx=0;
	fo(i,0,9) if(i^d) mx=max(mx,s[i]);
	fo(j,0,k)
		if(s[d]+j>mx)
			ans+=c[k][j]*calc(k-j,s[d]+j);
	return ans;
}
inline ll check()
{
	int mx=0;
	fo(i,0,9) if(i^d) mx=max(mx,s[i]);
	return s[d]>mx;
}
ll dfs(int k,bool limit,bool flag)
{
	if(!limit&&flag) return work(top-k+1);
	if(k>top) return check();
	int mx=limit?st[k]-1:9;
	bool nex;
	ll ans=0;
	fo(i,0,mx) 
	{
		nex=flag|(i!=0);
		if(nex) s[i]++;
		ans+=dfs(k+1,0,nex);
		if(nex) s[i]--;
	}
	if(limit)
	{
		s[st[k]]++;
		ans+=dfs(k+1,1,1);
		s[st[k]]--;
	}
	return ans;
}

inline ll solve(ll r)
{
	if(!r) return 0;
	fo(i,0,9) st[i]=0;
	for(top=0;r;st[++top]=r%10,r/=10);
	reverse(st+1,st+top+1);
	return dfs(1,1,0);
}
ll l,r;
int main()
{
	init();
	CASET
	{
		l=read(); r=read(); d=read();
		printf("%lld\n",solve(r)-solve(l-1));
	}
	return 0;
}