SGU160 解题手记
　　记前k个数字能凑出来的分数的集合为S[k]，将S[k]中每个分数 * 第k+1个数字 Mod M加入S[k+1]，再把S[k]中的分数并入S[k+1]，这时S[k+1]就是前k+1个数字能凑出来的分数了。
　　Submit 1: AC。

?[Copy to clipboard]View Code CPP
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

#include <cstdio>
#include <algorithm>
using namespace std;
 
int main()
{
    bool score[2][1000]={{0,1}},pull[10001]={};
    int source[1000]={},factor[1000]={};
    int n,m,maxscore(1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
    {
        int p,tmaxscore=maxscore;
        scanf("%d",&p);
        memcpy(score[i&1],score[(i-1)&1],maxscore+1);
        for (int j=1;j<=maxscore;++j) if (score[(i-1)&1][j] && !score[(i-1)&1][j*p%m])
        {
            score[i&1][j*p%m]=true;
            factor[j*p%m]=i; source[j*p%m]=j;
            tmaxscore=max(tmaxscore,j*p%m);
        }
        maxscore=tmaxscore;
    }
    for (int i=maxscore;factor[i];i=source[i]) pull[factor[i]]=true;
    printf("%d\n",maxscore);
    for (int i=1;i<=n;++i) if (pull[i])
        printf("%d ",i);
}