NOIP 2004 数字游戏（虫食算）

下面程序可计算如下形式的式子：

1
2
3
4
5
6
7
8
9
10
11
one
+  nine
+ fifty
+twenty
-------
eighty

a
+a
--
bc

方法是枚举进位+解方程，涉及的字母以及各个位上的进位作为变量，然后解方程。这样可以用　各个位上的进位　和　字母变量中的自由变量　表示　其他字母变量。枚举　各个位上的进位　和　字母变量中的自由变量　以求出　其他字母变量，以此得到各组解。使用方法：根据要求解的式子设置各个变量，N、M设置得大点没关系，L要正好等于式子的行数，然后输入L行字符串

举例：

1
2
3
N=10（10个变量）
M=6（一行最大长度6）
L=5（5行）

输入

1
2
3
4
5
one
nine
fifty
twenty
eighty
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
116
117
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
using namespace std;

const int N = 10; //maximum number of variables
const int M = 6; //maximum line length
const int L = 3; //number of lines
string s[L];
int len[L], mapping[256];
int m = 0, n = 0, res;
int pi[N], x[M+N], a[M][M+N], d[M];
vector<int> fre;

int gcd(int x, int y)
{
        int t;
        x = abs(x);
        y = abs(y);
        while (y) t = x%y, x = y, y = t;
        return x;
}

bool GaussJordanElimination()
{
        memset(pi, 0xFF, sizeof(pi));
        for (int i = 0; i < m; ++i)
        {
                int pivot = i;
                if (!a[i][i])
                {
                        for (int j = 0; j < n; ++j)
                                if (a[i][j]) pivot = j;
                        if (pivot == i) continue;
                }
                pi[pivot] = i;
                for (int j = 0; j < m; ++j)
                        if (j != i && a[j][pivot])
                        {
                                int lcm = a[i][pivot] / gcd(a[i][pivot], a[j][pivot]) * a[j][pivot], k1 = lcm/a[i][pivot], k2 = lcm/a[j][pivot];
                                for (int k = 0; k < m+n; ++k)
                                        a[j][k] = a[j][k]*k2-a[i][k]*k1;
                        }
        }
        for (int i = 0; i < n; ++i)
                if (pi[i] == -1)
                        fre.push_back(i);
}

void DFS_left(int k)
{
        if (k == fre.size())
        {
                for (int i = 0; i < n; ++i)
                        if (pi[i] != -1)
                        {
                                int t = 0;
                                for (int j = 0; j < fre.size(); ++j)
                                        t -= a[pi[i]][fre[j]]*x[fre[j]];
                                for (int j = 0; j < m; ++j)
                                        t -= a[pi[i]][n+j]*x[n+j];
                                if (t%a[pi[i]][i]) return;
                                x[i] = t/a[pi[i]][i];
                                if (x[i] < 0 || x[i] >= 10) return;
                        }
                for (int i = 0; i < L; ++i)
                {
                        for (int j = m-s[i].size(); j; --j) printf("   ");
                        for (string::iterator it = s[i].begin(); it != s[i].end(); ++it)
                                printf("%3d", x[mapping[*it]]);
                        puts("");
                }
                puts("");
                ++res;
        }
        else for (int i = 0; i < 10; ++i)
                         x[fre[k]] = i, DFS_left(k+1);
}

void DFS_right(int k)
{
        if (k == m)
                DFS_left(0);
        else for (int i = 0; i < L-1; ++i)
                         x[n+k] = i, DFS_right(k+1);
}

int main()
{
        memset(mapping, 0xFF, sizeof(mapping));
        memset(a, 0, sizeof(a));
        for (int i = 0; i < L; ++i)
        {
                cin >> s[i];
                if (s[i].size() > m) m = s[i].size();
                for (int j = 0; j < s[i].size(); ++j)
                {
                        if (mapping[s[i][j]] == -1)
                                mapping[s[i][j]] = n++;
                        a[s[i].size()-1-j][mapping[s[i][j]]] += i == L-1 ? -1 : 1;
                }
        }

        for (int i = 0; i < m; ++i)
        {
                if (i) a[i][n+i] = 1;
                if (i < m-1) a[i][n+i+1] = -10;
        }
        GaussJordanElimination();
        res = 0;
        DFS_right(1);
        printf("\n%d solution(s).\n", res);
}