今日SGU 6.5

sgu 160

题意：给你n个数字 数字范围 1 到 m 问你从中取出任意数量的数字使得这些数字的积取模m最大

收获：dp，记录dp的路径

#include<bits/stdc++.h>

#define de(x) cout<<#x<<"="<<x<<endl;

#define dd(x) cout<<#x<<"="<<x<<" ";

#define rep(i,a,b) for(int i=a;i<(b);++i)

#define repd(i,a,b) for(int i=a;i>=(b);--i)

#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)

#define ll long long

#define mt(a,b) memset(a,b,sizeof(a))

#define fi first

#define se second

#define inf 0x3f3f3f3f

#define INF 0x3f3f3f3f3f3f3f3f

#define pii pair<int,int>

#define pdd pair<double,double>

#define pdi pair<double,int>

#define mp(u,v) make_pair(u,v)

#define sz(a) (int)a.size()

#define ull unsigned long long

#define ll long long

#define pb push_back

#define PI acos(-1.0)

#define qc std::ios::sync_with_stdio(false)

#define db double

#define all(a) a.begin(),a.end()

const int mod = 1e9+;

const int N = 1e4+;

const double eps = 1e-;

using namespace std;

bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }

bool ls(const db &a, const db &b) { return a + eps < b; }

bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }

ll gcd(ll a,ll b) { return a==?b:gcd(b%a,a); };

ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }

ll kpow(ll a,ll b) {ll res=;a%=mod; if(b<) return ; for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}

ll read(){

    ll x=,f=;char ch=getchar();

    while (ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//inv[1]=1;

//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

int a[N];

bool dp[];

pii pre[];

void out(int j){

//    de(j)

    if(!pre[j].fi) {

        printf("%d ",pre[j].se);

        return ;

    }

    out(pre[j].fi);

    printf("%d ",pre[j].se);

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    rep(i,,n+) scanf("%d",a + i),a[i] %= m;

    rep(i,,n+) rep(j,,m) {

        if(dp[j]&&!dp[j*a[i]%m]&&pre[j].se!=i){

            dp[j*a[i]%m] = true; pre[j*a[i]%m] = mp(j,i);

        }

        if(!dp[a[i]]) dp[a[i]] = true,pre[a[i]] = mp(,i);

    }

    repd(i,m,) if(dp[i]) {

        if(i) printf("%d\n",i);

        out(i);

        return ;

    }

    return ;

}