dp [ x ] [ y ] [ z ] 表示二进制y所表示的组合对应的之和mod x余数为z的最小数...

如可用的数字为 1 2 3 4...那么 dp [ 7 ] [ 15 ] [ 2 ] = 1234 ....

输入一个数列后..将dp的表做出来..然后O(1)的输出...题目要求是( T + X ) % K =0 可以转化为 T % K = ( K - ( X % K ) ) % K

Program:

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<set>

#include<algorithm>

#include<cmath>

#define oo 1000000007

#define ll long long

#define pi acos(-1.0)

#define MAXN 505

using namespace std;

int n,a[10],dp[102][520][102],num,ans[10];

bool legal(int k)

{

      int x=1,i;

      for (i=0;i<n;i++)

      {

             if (k%2) x=a[i];

             k/=2;

      }

      return x;

}

int main()

{

      int i,m,X,K,j,t,p;

      while (~scanf("%d%d",&n,&m))

      {

             for (i=0;i<n;i++) scanf("%d",&a[i]);

             sort(a,a+n);

             memset(dp,-1,sizeof(dp));

             for (K=1;K<100;K++)

             {

                    dp[K][0][0]=0;

                    for (i=0;i<(1<<n);i++)

                      if (legal(i))

                        for (j=0;j<n;j++)

                          if ( (i & (1<<j)))

                            for (t=0;t<K;t++)

                              if (dp[K][i-(1<<j)][t]!=-1)

                              {

                                    p=dp[K][i-(1<<j)][t]*10+a[j];

                                    if (dp[K][i][(t*10+a[j])%K]==-1 || dp[K][i][(t*10+a[j])%K]>p)

                                       dp[K][i][(t*10+a[j])%K]=p;

                              }

             }

             while (m--)

             {

                    scanf("%d%d",&X,&K);

                    if (dp[K][(1<<n)-1][(K-(X%K))%K]==-1) printf("None\n");

                       else printf("%d\n",dp[K][(1<<n)-1][(K-(X%K))%K]);

             }

      }

      return 0;

}