荔枝丹(litchi)

【from new_dtoj 3979: 荔枝丹(litchi)】
题目描述
绛雪艳浮红锦烂，玉壶光莹水晶寒。
高名已许传新曲，芳味曾经荐大官。
乌府日长霜署静，几株斜覆石栏杆。
——明·陈辉《荔枝》

荔枝（丹），拼音为lizhidan，一种好吃的水果，深得悦色老师的喜爱。
祝阿姨得到了许多许多的荔枝丹，每个荔枝丹上都有一个0到9之间的数字。祝阿姨把它们分成许多组，每组表示一个数，且所有组表示的数字合起来恰好是[L,R]内的所有数。
祝阿姨知道悦色老师特别喜欢吃荔枝丹，于是邀请了悦色老师来吃荔枝丹。悦色老师最喜欢吃有数字0的荔枝丹了，她吃掉了所有数字为0的荔枝丹。
祝阿姨想知道还剩下多少不同的组。注意悦色老师吃完后，荔枝丹就无序了，也就是说123和321是同样的组。
其中R<=1e18
题解：
妙啊！
如果补上前缀0，使得所有数字位数相等，并把数字看成字符串，并把字符排序，那么问题等价于有多少不同的字符串。
如果R=1e18，特判即可即L<=R<1e18
因为不同字符串的数目不是很多（C(27,9)=4686824），所以我们可以暴力求出每个字符串，然后快速判断这个字符串能否被[L,R]中的某个数构造出来
设Fp,lf,rfF_{p,lf,rf}Fp,lf,rf/span>表示到了第p位，前面的位数为L/R的前缀能否满足
LiL_iLi/span>表示L第i位的数字（从高到低），RiR_iRi/span>类似
分类讨论即可，下面举lf=rf=1的情况

1. 如果LpL_pLp/span>==RpR_pRp/span>，那么第p位上只能填上LpL_pLp/span>，判断合法往下递归即可
2. 否则LpL_pLp/span><RpR_pRp/span>，如果在第p位上填上[Lp+1,Rp][L_p+1,R_p-1][Lp/span>+1,Rp/span>/span>1]，则这个字符串一定满足，否则就看这一位上填的是LpL_pLp/span>还是RpR_pRp/span>，有一方满足即满足

剩下两类也是一样的，懒得分了
效率玄学，不懂为啥很快s>（dtoj评测机强大）
具体见代码

相关资源：Ztrans丹诚软件Z39.50客户端-其它工具类资源-CSDN文库