POJ 1426 Find The Multiple

题意：给一个整数n，求一个不超过100个数字的，只由01组成的，是n的倍数的，非0十进制整数。

解法：dp。考虑dp[i][j]表示i个数组成的数modn为j的可能性，则有状态转移方程：foreach dp[i][j]:dp[i + 1][j × 10 % n] = 1, dp[i + 1][(j × 10 + 1) % n] = 1。再用一个数组记录转移的路径，倒着找回去就是答案了。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<iomanip>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

using namespace std;

int dp[105][205], path[105][205];
int main()
{
    int n;
    while(~scanf("%d",&n) && n)
    {
        if(n == 1)
        {
            puts("1");
            continue;
        }
        int ed = -1;
        memset(dp, 0, sizeof dp);
        memset(path, -1, sizeof path);
        dp[0][0] = 1;
        for(int i = 0; i < 100 && ed == -1; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!dp[i][j]) continue;
                if(j == 0)
                {
                    dp[i + 1][0] = 1;
                    path[i + 1][0] = 0;
                    dp[i + 1][1] = 1;
                    path[i + 1][1] = 0;
                }
                else
                {
                    int r = j * 10;
                    dp[i + 1][r % n] = 1;
                    path[i + 1][r % n] = j;
                    if(r % n == 0) {ed = i + 1; break;}
                    r++;
                    dp[i + 1][r % n] = 1;
                    path[i + 1][r % n] = j;
                    if(r % n == 0) {ed = i + 1; break;}
                }
            }
        }
        string ans;
        int x = 0;
        for(int i = ed; i > 0; i--)
        {
            if((path[i][x] * 10) % n == x) ans += '0';
            else ans += '1';
            x = path[i][x];
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
    return 0;
}