一道不难但是很坑的题.
有00112233445566778899这20个数字,你要组成没有前导零的数,问有多少个数满足被11整除.
网上查阅资料得知偶数位和与奇数位和做差的值模11结果为0就可以,所以我们考虑爆搜所有奇数偶数的排列,然后组合在一起枚举情况.注意不能有前导零.
时间复杂度 $O(2^{20})$
因为少算情况WA了好几发.
exp:

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
u128 fac[100];
int st[21];
bitset<21> vis;

vector<bitset<21>> a;

void dfs(int num,int l,int r,int cl,int cr){
	if(num>20){
		if(abs(l-r)%11==0&&cl==cr&&cl==10){
			a.push_back(vis);
		}
		return;
	}
	dfs(num+1,l+st[num],r,cl+1,cr);
	vis[num]=1;
	dfs(num+1,l,r+st[num],cl,cr+1);
	vis[num]=0;
}
i128 n,m,res,ar0,ar1,ar2;

array<char,10>ty;
map<array<char,10>,i128>mp;

//#define NaraFluorine
int main(){
	fac[0]=1;
	for(int i=1;i<=30;++i)fac[i]=fac[i-1]*i;
	for(int i=1;i<=20;++i){
		st[i]=(i-1)>>1;
	}
	ar2=fac[10]*(72)*fac[8];
	ar1=fac[10]*fac[9]*9;
	ar0=fac[10]*fac[10];
	dfs(1,0,0,0,0);
	for(auto i:a){
		for(int j=0;j<=9;++j){
			ty[j]=0;
		}
		for(int j=1;j<=20;++j){
			if(i[j]==1){
				ty[st[j]]++;
			}
		}
		if(i[1]==0){
			if(i[2]==0){//偶数位两个0
				mp[ty]=ar2;
			}else{//偶数位一个0
				mp[ty]=ar1;
			}
		}else{
			if(i[2]==0){//偶数位一个0
				mp[ty]=ar1;
			}else{//偶数位没有0
				mp[ty]=ar0;
			}
		}
	}
	int cnt=0;
	for(auto i:mp){
		cnt++;
		i128 tmp=i.second;
		for(int j=0;j<=9;++j){
			if(i.first[j]==0||i.first[j]==2){
				tmp>>=1;
			}
		}
		res+=tmp;
	}
	fout<<res;
	return 0;
}