POJ 1426 Find The Multiple(背包方案统计)

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

Sample Output

10
100100100100100100
111111111111111111

思路:

1. 抽象成背包, 把0,1 串具体化, 变成 1, 10, 100, 1000

这里有两个好处:

第一, 每个数字都是唯一的, 任何数字不是另一个数字的前导, 抽象成背包问题

第二, 任何01串都可以用上述的数字表示出来. 比如, 111 = 100 + 10 + 1, 1110 = 1000+ 111

上面这个技巧, 在背包问题的一个优化中讨论过. 非常巧妙

2. dp[i][j] 表示前 i 个(1, 10, 100... 10^i) 组成的数字模 n 的余数 j 的最小值, 当该最小值不存在时, dp[i][j] = 0

　　比如, 当 n = 6 时, dp[1][4] = 10. dp[1][5] = 11. dp[2][2] = 110

3. dp[i][j] = min(dp[i-1][j], dp[i-1][r]+10^i), 其中 r 也是余数, 当 j 等于0 且 dp[i][j] 不等于 0 时, 得到解

　　表示以上一层 (i-1) 的余数 r 作为支点更新 dp[i][j], 原理是:

　　已知 r = dp[i-1][r]%n

　　dp[i][(r + 10^i)%N] = dp[i-1][r] + 10^i 其中 j = (r + 10^i)%N

4. (3) 的求解过程中每次求解 (10^i)%n 太过复杂, 可以根据模定理进行优化

　　定理: (a%n + b%n)%n == (a+b)%n, (a%n * b%n)%n == (a*b)%n

　　可以使用上述定理简化以减少计算量

　　比如, 已知 10%6 == 4, 那么 100%6 == (10*10)%6 == (10%6*10%6)%6 == (4*10%6)%6 == (4%6*10%6)%6 == (4*10)%6 == 4

　　1000%6 == (100*10)%6 == (100%6*10%6)%6 == (4*10%6)%6 == 4

总结:

1. 发现一个错误: 一样的代码, 返回不一样的结果. 原因: int 越界

        exp *= 10;
        rem = (rem * 10) % n;   // 模运算定理
        printf("exp = %lld, rem = %d
", exp,rem);

　　返回的是 10, 4 (correct)

但是

        exp *= 10;
        rem = (rem * 10) % n;   // 模运算定理
        printf("exp = %d, rem = %d
", exp,rem);

　　返回的总是 10, 0 (wrong)

2. 任意的01串转化为1, 10, 100... 的组合, 从而抽象为01背包. 同时使用了一个简化计算 10^i 的技巧, 使得3个小时才看懂50行代码

代码:

代码写的不能再精髓了, 我了解思路后开始码, 但改过来改过去, 越改越觉得下面的代码精髓

1. 初始化, dp[i][r] == 0 表示没有满足条件的数, 同时省去了 dp[0][0] 的赋值

2. 17, 18, 23, 24行的代码, 保证了 min

3. 21 行, r==0 时的特殊性, 只有 r=0 时, 才能增加一个值

#include <iostream>
using namespace std;

const int MAXN = 210;
int n;
long long int dp[MAXN][MAXN];
/*
 *	dp[i][r] 表示前 i 个数组成的数字模 n 等于 r 的最小值
 *	dp[i][r] = min(dp[i-1][r], dp[i][r']+10^i) 以 r' 为支点更新 dp[i][r]
 */
long long int solve_dp() {
	dp[0][1] = 1;
	long long int rem = 1, exp = 1;
	for(int i = 1; i < MAXN; i ++) {
		exp = exp*10;
		rem = (rem*10)%n;
		for(int r = 0; r < n; r ++) // 继承
			dp[i][r] = dp[i-1][r];	
		
		for(int r = 0; r < n; r ++) {
			if(dp[i-1][r] || r == 0) {	//r == 0 比较特殊, 唯一一个可能用于更新的状态的值, 即使 dp[i-1][r] = 0, 去求 dp[i][r] 仍是必要的
				long long int newr = (r + rem)%n;
				if(dp[i][newr] == 0) 
					dp[i][newr] = exp + dp[i-1][r];	// 首次更新, 保证了最小性
				if(newr == 0)
					return dp[i][0];
			}
		}
	}
}
int main() {
	freopen("E:\Copy\ACM\测试用例\in.txt", "r", stdin);
	while(cin >> n && n != 0) {
		if(n == 1)
			cout << 1 << endl;
		else
			cout << solve_dp() << endl;
	}
	return 0;
}

update 2014年3月14日21:00:58

1. r = 0 时的特殊性. r = 0 的特殊性体现在 dp[i][0] = 0 和余数为 0 的双重意义. 余数为 0 表示不存在某个数对 n 取模为 0. 而 dp[i][0] = 0 又起到了初始化的作用, 使得对于一个数, 比如 100, dp[i][100%n] = 0 + 100. 这个 0 就用 dp[i][0] 取代了, 相当于代码重用