Gym100825C-KenKen-You-Do-It题解

发表于 分类于

题目传送门

题意：在一个矩阵上选中了若干个格子，保证连通。你需要在这些格子中填数，使得：每行每列不能重复，且这些数进行给定运算（可以认为只有加法和乘法）的结果为给定的数值。求填数的方案数。

首先考虑朴素的搜索。将选中的格子按行列排序（顺序剪枝），依次考虑每个格子填的数，中途维护每行每列的数字使用情况（可以状压），进行可行性剪枝。这个做法虽然可以通过本题，但跑得非常慢且需要卡常。

考虑进一步优化。我们发现，“运算结果固定”这条限制与数字摆放顺序无关，而只与使用的数字集合有关；“每行每列不重复”这条限制只与数字摆放顺序和位置之间是否相同有关，而与具体数字无关。于是这两部分可以分开考虑。

假设只考虑后一条限制，我们预处理出对于每一种“数字区分集合”（即有多少个不同的元素，每个不同的元素各用了多少次，而不关心到底是多少）的摆放方案数。这个可以使用搜索来计算：搜索每个位置，维护当前用了几个数字以及第几个数字用的次数，每次考虑这个位置放以前的哪个数字或新开一个数字使用。对于“数字区分集合”可以使用“每个数字用的次数”的 vector 排序后来表示（相同的 vector 意味着相同的“区分集合”）。可以使用 map<vector<int>,int> 来记录。

然后考虑第一条限制。此时与摆放顺序无关，考虑使用哪些数字集合。这个也可以使用搜索，由于此时没有顺序限制，可以强制从小到大填数（大幅减少状态数）。当确定了一个数字集合时，使用预处理出来的“该摆放集合的方案数”可快速得到答案。注意对于出现次数相同的两个数，可以任意交换顺序，所以答案需要对每个出现次数相同的数的个数求阶乘，相乘得到最终答案。

By cxm1024 From RNS3

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
#include<bits/stdc++.h>
using namespace std;
int n,m,t,jc[11],ans=0;
char ch;
int x[15],y[15];
map<vector<int>,int> mp;
int cnt[15],xvis[15],yvis[15];
void init(int now,int tot) {
    if(now==0) {
        vector<int> v;
        for(int i=1;i<=tot;i++)
            v.push_back(cnt[i]);
        sort(v.begin(),v.end());
        mp[v]++;
        return;
    }
    for(int i=1;i<=tot+1;i++) {
        if(xvis[x[now]]&(1<<i)) continue;
        if(yvis[y[now]]&(1<<i)) continue;
        cnt[i]++;
        xvis[x[now]]^=(1<<i),yvis[y[now]]^=(1<<i);
        init(now-1,max(tot,i));
        cnt[i]--;
        xvis[x[now]]^=(1<<i),yvis[y[now]]^=(1<<i);
    }
}
void dfs1(int now,int sum,int bd) {
    if(now==0) {
        if(sum!=0) return;
        vector<int> v;
        for(int i=1;i<=n;i++)
            if(cnt[i]) v.push_back(cnt[i]);
        sort(v.begin(),v.end());
        int res=mp[v],lst=0;
        for(int i=1;i<v.size();i++)
            if(v[i]!=v[i-1]) res*=jc[i-lst],lst=i;
        res*=jc[v.size()-lst];
        ans+=res;
        return;
    }
    if(sum>now*n||sum<now) return;
    for(int i=bd;i<=n;i++) {
        cnt[i]++;
        dfs1(now-1,sum-i,i);
        cnt[i]--;
    }
}
void dfs2(int now,int sum,int bd) {
    if(now==0) {
        if(sum!=1) return;
        vector<int> v;
        for(int i=1;i<=n;i++)
            if(cnt[i]) v.push_back(cnt[i]);
        sort(v.begin(),v.end());
        int res=mp[v],lst=0;
        for(int i=1;i<v.size();i++)
            if(v[i]!=v[i-1]) res*=jc[i-lst],lst=i;
        res*=jc[v.size()-lst];
        ans+=res;
        return;
    }
    for(int i=bd;i<=n;i++) {
        if(sum%i!=0) continue;
        cnt[i]++;
        dfs2(now-1,sum/i,i);
        cnt[i]--;
    }
}
signed main() {
    jc[0]=1;
    for(int i=1;i<=10;i++)
        jc[i]=jc[i-1]*i;
    cin>>n>>m>>t>>ch;
    for(int i=1;i<=m;i++)
        cin>>x[i]>>y[i];
    if(ch=='-') {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&(i-j==t||j-i==t))
                    ans++;
        cout<<ans<<endl;
        return 0;
    }
    if(ch=='/') {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&(j*t==i||i*t==j))
                    ans++;
        cout<<ans<<endl;
        return 0;
    }
    init(m,0);
    if(ch=='+') dfs1(m,t,1);
    else dfs2(m,t,1);
    cout<<ans<<endl;
    return 0;
}