Bus Number习题解析 （二进制枚举 + 组合数学 or DFS）

Bus Number习题解析 （二进制枚举 + 组合数学 or DFS）

Vasya模糊的记得公交车车牌号码为n≤1018" role="presentation">n≤1018$n\le {10}^{18}$，但是他不会漏掉某个数字，号码不允许以0开头，问可能的号码种数。
比如2028，可能的号码有208，280，802，820，2028，2082，2208，2280，2802，2820，8022，8202，8220。
但028和128都是不合法的。

思路

知道这个以后就可以暴力了，二进制枚举n的所有子集，然后统计所有子集的情况就是答案。
子集可能会漏掉某个数字导致不合法，所以我们应该判断该子集是否合法。
两个子集选的数字可能相同，会重复导致多算，所以我门应该用set判重，如果之前算过就不算这种情况了。
还有就是前导0的情况，所以我们计算的时候先把所有的情况算出来，如果含有前导0的情况，我们就把前导0的情况减去就好了。

#include
using namespace std;
typedef long long ll;
int a[15], vis[15];
ll fac[20];
set s;
void split(string x, int *a)
{
 for (int i = 0; i < 10; i++) a[i] = 0;
 for (char i: x) a[i-'0']++;
}
ll getcount()//去重全排列
{
 ll ans = fac[accumulate(a, a+10, 0)];
 for (int i = 0; i < 10; i++) ans /= fac[a[i]];
 return ans;
}
ll getans(string x)
{
 split(x, a);
 for (int i = 0; i < 10; i++) if (vis[i] && !a[i]) return 0;//比原来少了i数字
 sort(x.begin(), x.end());
 if (s.count(x)) return 0;//x这种子集算过了
 else s.insert(x);

 ll ans = getcount();
 if (a[0]) { a[0]--; ans -= getcount(); }//减去前导0情况
 return ans;
}
int main()
{
 fac[0] = 1; for(int i = 1; i < 20; i++) fac[i] = fac[i-1]*i;//计算阶乘
 string n; cin >> n;
 split(n, vis);
 int k = n.size();
 ll ans = 0;
 for (int i = 1; i < (1<