2010年02月08日星期一.sgu160 pku2206
本人WA@ test case 8了几次，最后才发现原来输出要按照序号的升序。。。
仔细读题。。。
dp,可一维，可二维。一维的更好想，更好写，更快
其实如果没有取模的运算，完全就是一个背包的变形问题。
看下例：一个数x，乘以y取模之后可以比x大也可能比x小
......x......
....x.....x..
所以，不论是按照x升序扫描,还是降序扫描都有可能取到当前数产生的状态。
如果写二维dp就没有这个问题了。如果要写成一维dp可以记录一下这个状态是第几个数
产生的，状态转移的时候只处理由当前数之前的数生成的状态。
1
2 const int M = 1024;
3 int idx[M];
4 int pre[M];
5 int lev[M];
6 int out[M],top = 0;
7 int m,n;
8 int main()
9 {
10 int i,j,k;
11 scanf("%d%d",&n,&m);
12 pre[1] = 1;
13 lev[1] = 1;
14 for (i = 1;i <= n;i++) {
15 scanf("%d",&k);
16 for (j = 1;j <= m;j++) {
17 if (pre[j] && lev[j] <= i) {
18 int t = (j * k) % m;
19 if (!pre[t]) {
20 lev[t] = i + 1;
21 pre[t] = j;
22 idx[t] = i;
23 }
24 }
25 }
26 }
27 for (i = m - 1;i >= 1;i--) {
28 if (pre[i]) {
29 printf("%d\n",i);
30 break;
31 }
32 }
33 while (i != 1) {
34 out[top++] = idx[i];
35 i = pre[i];
36 }
37 sort(out,out + top);
38 for (i = 0;i < top;i++) {
39 printf("%d ",out[i]);
40 }
41 printf("\n");
42 return 0;
43 }
44