给出一个<1e18的数， 求将他的各个位的数字交换后， 能整除m的数的个数。
用状态压缩记录哪个位置的数字已经被使用了， 具体看代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 int digit[20], m, cnt; 20 ll dp[1<<18][101]; 21 ll dfs(int s, int num) { //s是当前状态， num是模m剩余的数 22 if(num==0&&s==0) 23 return 1; 24 if(~dp[s][num]) 25 return dp[s][num]; 26 int used[10]; 27 mem(used); 28 ll ret = 0; 29 for(int i = 0; i<cnt; i++) { 30 if(!(s&(1<<i))) //如果这一位已经被使用了就直接continue 31 continue; 32 if(used[digit[i]]) 33 continue; 34 used[digit[i]] = 1; 35 ret += dfs(s^(1<<i), (num*10+digit[i])%m); 36 } 37 return dp[s][num] = ret; 38 } 39 int main() 40 { 41 int num[12]; 42 mem(num); 43 mem1(dp); 44 ll n; 45 cin>>n>>m; 46 while(n) { 47 digit[cnt++] = n%10; 48 n/=10; 49 } 50 ll ans = 0; 51 ll s = (1<<cnt)-1; //初始全都没有被使用 52 for(int i = 0; i<cnt; i++) { 53 if(digit[i]) { 54 if(num[digit[i]]) //某一位上的数不能够重复计数 55 continue; 56 num[digit[i]] = 1; 57 ans += dfs(s^(1<<i), digit[i]%m); //s^(1<<i)说明第i位被使用了 58 } 59 } 60 cout<<ans<<endl; 61 return 0; 62 }