Sgu/160

C

//by mx
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 10000
#define MAXM 1000
#define MAX(x,y) ((x)>(y)?(x):(y))
#define ABS(x) (MAX(x,-(x)))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define oo 1e9
#define R return
typedef struct
{
	long pdata,pnum;
}data;
data pre[MAXM+10]={0};
long n,m,a[MAXN+10]={0},f[MAXM+10]={0},ansn,ans[MAXN+10]={0},ans1;
void init()
{
	long i;
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=n;i++)
	    scanf("%ld",&a[i]);
	R;
}
int cmp(const void *x,const void *y)
{
	R *(long*)x-*(long*)y;
}
void dp()
{
	long i,j;
	f[1]=1;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		    if (f[j]&&pre[j].pnum!=i&&!f[j*a[i]%m])
		    {
				f[j*a[i]%m]=1;
				pre[j*a[i]%m].pdata=j;
				pre[j*a[i]%m].pnum=i;
			}
	}
	for (i=m-1;i>=1;i--)
	{
		if (f[i])
		{
			ans1=i;
			break;
		}
	}
	ansn=0;
	for (i=ans1;i!=1;i=pre[i].pdata)
		ans[++ansn]=pre[i].pnum;
	qsort(ans+1,ansn,sizeof(long),cmp);
	R;
}
void output()
{
	long i;
	printf("%ld\n",ans1);
	for (i=1;i<=ansn;i++)
	    printf("%ld%c",ans[i],i==ansn?'\n':' ');
	R;
}
int main()
{
	init();
	dp();
	output();
	R 0;
}

CPP

一直被卡内存。。。

//by a710128
#include<iostream>
using namespace std;
short f[20005][1001],a[10005],n,m,ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	f[0][1]=-1;
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<m;j++)
			if(f[i*2][j]) {f[(i+1)*2][j]=j;f[(i+1)*2+1][(j*a[i+1])%m]=j+m;}
		for(int j=1;j<m;j++)
			if(f[i*2+1][j]) {f[(i+1)*2][j]=j+m*2;f[(i+1)*2+1][(j*a[i+1])%m]=j+m*3;}
	}
	for(ans=m;ans>=1;ans--)
		if(f[n*2+1][ans]){ans+=m*2;break;}
		else if(f[n*2][ans]) break;
	cout<<ans%m<<endl;
	for(int i=n;i>=0;i--)
		if(ans<m) ans=f[i*2][ans];
		else if(ans<m*2){a[++a[0]]=i+1; ans=f[i*2][ans%m];}
		else if(ans<m*3) ans=f[i*2+1][ans%m];
		else {a[++a[0]]=i+1;ans=f[i*2+1][ans%m];}
	for(int i=a[0];i>=1;i--) cout<<a[i]<<" ";
	return 0;
}