UVa11084
題敘
http://domen111.github.io/UVa-Easy-Viewer/?11084
想法
先暴力枚舉出數字的排列組合
再個別轉換成數字比較是否可以整除
Code
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
| #include<bits/stdc++.h> #define LL long long #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define pii pair<int,int> using namespace std; int t,d,ans,cnt[10]; string s; void dfs(int depth, long long res){ if(depth == s.size()){ if(res%d == 0){ ans++; } return; } for(int i=0 ; i<10 ; i++){ if(cnt[i]>0){ cnt[i]--; dfs(depth+1, res*10 + i); cnt[i]++; } } } int main(){ IOS cin>>t; while(t--){ for(int i=0 ; i<10 ; i++) cnt[i]=0; ans=0; cin>>s>>d; for(int i=0 ; i<s.size() ; i++){ cnt[s[i]-'0']++; } dfs(0,0); cout<<ans<<"\n"; } return 0; }
|
複雜度
- 初始化
$O(MaxN)$
- DFS
$O(len(s)!)$ (len(s)最大為10)
整體複雜度: $O(tN!)$