给出n,m。从n个数中选几个相乘，再%m。能取到的最大值和取法。
用dp[i][j]记录前i行能否取到j这个结果。那么dp[i][j]至少等于dp[i-1][j]，还能等于所有的dp[i-1][j]*arr[i]%m。要输出方案，那么如果在记录的过程中，j*arr[i]%m在i-1没出现说明是新得出的，且一定取了i号，那么p[j*arr[i]%m]=j。输出结果时往上回溯。
//#pragma comment(linker,"/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include <stack> #include <iomanip> using namespace std; typedef long long lon; const lon SZ=10010,INF=0x7FFFFFFF; const double EPS=1e-8; int arr[SZ],p[SZ]; bool vst[SZ][1010]; int main() { //std::ios::sync_with_stdio(0); //freopen("d:\\1.txt","r",stdin); //for(;scanf("%d",&n)!=EOF;) lon casenum; //cin>>casenum; //for(lon time=1;time<=casenum;++time) { int n,m; cin>>n>>m; for(int i=1;i<=n;++i)cin>>arr[i]; vst[0][1]=1; for(int i=1;i<=n;++i) { copy(vst[i-1],vst[i-1]+m,vst[i]); for(int j=0;j<m;++j) { if(vst[i-1][j]) { if(vst[i][j*arr[i]%m]==0) { vst[i][j*arr[i]%m]=1; if(i==1||vst[i-1][j*arr[i]%m]==0) { p[j*arr[i]%m]=j; } } } } } int pos=0; for(int i=m-1;i>=0;--i) { if(vst[n][i]) { pos=i; break; } } if(pos==1)cout<<pos<<endl; else { vector<int> res; int cur=pos; cout<<cur<<endl; for(int i=n;i>=1;--i) { if(vst[i][cur]^vst[i-1][cur]) { res.push_back(i); cur=p[cur]; } } sort(res.begin(),res.end()); for(int i=0;i<res.size();++i) { if(i)cout<<" "; cout<<res[i]; }cout<<endl; } } return 0; }
sgu 160 Magic Multiplying Machine
原文：https://www.cnblogs.com/gaudar/p/9784214.html