一个简单组合问题

发表于 |

在计蒜之道群里面，有同学提了一个问题，如下：

  1. 使用 $0$~$9$ 中的数字，不重复，不遗漏
  2. 将数字分成任意段，每段都应是一个平方数（可以是0但无前置0）
  3. 段的顺序不影响结果。例如 $1\;4$ 和 $4\;1$ 是同一组，计 $1$

问能组成多少种这样的平方数组合？

本渣实在太弱，一开始写很傻逼的 for 循环，后来又写了很复杂很容易错的 bfs 做法，其实根本就不需要，直接 dfs，哎是在太弱了。当然这个问题可以进化到任意进制里去。只要相应修改代码中的 $B$ 即可。

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//#pragma comment(linker,"/STACK:10240000,10240000") // C++ only
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
template<typename T>
void upmax(T &a,T b){ if(a<b) a=b;}
//typedef __int128 ll; // for g++
//const int INF =  0x3f3f3f3f;
//1e9+7,1e9+9,1e18+3,1e18+9 are prime
//479<<21|1=1004535809,17<<27|1=2281701377 and g=3
/*------ Welcome to my blog: http://dna049.com ------*/
const int N = 1e5+2;
const int B = 10;
LL a[N];
int sa[N],cnt[B],sz,n;
int check(LL x){
    int r = 0;
    for(int i=0;i<B;++i) cnt[i]=0;
    do{
        if(++cnt[x%B] == 2)   return 0;
        x/=B;++r;
    }while(x);
    return r;
}
int init(){
    int sz = 0;
    for(int i = 0;i<N;++i){
        LL t = LL(i)*i;
        int tmp = check(t);
        if(tmp){
            a[sz] = t;
            sa[sz++] = tmp;
        }
    }
    return sz;
}
void preadd(LL x, int p){
    do{
        cnt[x%B]+=p;
        x/=B;
    }while(x);
}
bool add(LL x, int p){
    preadd(a[x], p);
    n+=p*sa[x];
    bool flag = true;
    for(int i=0;i<B;++i){
        if(cnt[i]>1){
            flag = false;break;
        }
    }
    if(flag)    return true;
    preadd(a[x], -p);
    n-=p*sa[x];
    return false;
}
int ans,maxdep;
void dfs(int dep,int ed){
    if(n >= B || dep == maxdep){
        if(n==B)  ++ans;
        return;
    }
    for(int i=ed+1;i<sz;++i){
        if(!add(i,1))   continue;
        dfs(dep+1,i);
        add(i,-1);
    }
}
int getans(){
    for(int i=0;i<B;++i)    cnt[i]=0;
    for(int i=0;i<B;++i)    ++cnt[i*i%B];
    maxdep = 0;
    for(int i=0;i<B;++i){
        if(cnt[i]){
            cnt[i] = 0;
            ++maxdep;
        }
    }
    sz = init();
    ans = n = 0;
    for(int i=0;i<B;++i)   cnt[i]=0;
    dfs(0,-1);
    return ans;
}
int main(){
//        #define dna049 1
#ifdef dna049
    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
    LL time = clock();
#endif
//        freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    cout<<getans()<<endl;
#ifdef dna049
    printf("time: %f\n",1.0*(clock()-time)/CLOCKS_PER_SEC);
#endif
    return 0;
}

不过上面做法还是有点挫，好的做法是将用一个二进制数字表示状态即可，但是这样 $B$ 就不能取的太大。

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
72
73
74
75
76
77
78
79
//#pragma comment(linker,"/STACK:10240000,10240000") // C++ only
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
template<typename T>
void upmax(T &a,T b){ if(a<b) a=b;}
//typedef __int128 ll; // for g++
//const int INF =  0x3f3f3f3f;
//1e9+7,1e9+9,1e18+3,1e18+9 are prime
//479<<21|1=1004535809,17<<27|1=2281701377 and g=3
/*------ Welcome to my blog: http://dna049.com ------*/
const int N = 1e5+2;
const int B = 10;
LL a[N],s[N],sb;
int ans,sz;
LL check(LL x){
    LL r = 0;
    do{
        if(r & (1LL<<(x%B)))    return 0;
        r |= 1LL<<(x%B);
        x/=10;
    }while(x);
    return r;
}
void init(){
    sz = 0;
    for(int i=0;i<N;++i){
        a[sz] = LL(i)*i;
        LL t = check(a[sz]);
        if(t)   s[sz++] = t;
    }
    sb = 0;
    for(int i=0;i<B;++i)    sb |= 1LL<<i;
}
void dfs(LL q, int ed){
    if(q == sb){
        ++ans;return;
    }
    for(int i=ed+1;i<sz;++i){
        if(q&s[i])  continue;
        dfs(q|s[i],i);
    }
}
int getans(){
    if(!sz) init();
    dfs(0,-1);
    return ans;
}
int main(){
//        #define dna049 1
#ifdef dna049
    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
    LL time = clock();
#endif
//        freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    cout<<getans()<<endl;
#ifdef dna049
    printf("time: %f\n",1.0*(clock()-time)/CLOCKS_PER_SEC);
#endif
    return 0;
}