CF 2013-2014CTS01E04(Killer Challenge-将质因数存在 进行Bitmask)
首先，把P进行质因数分解，每一个不用的质因数压成1位
f[i][j]表示1前i位用j“拥有”的质因数表示。
然后都懂得。。。
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<functional>#include<cmath>#include<cctype>#include<cassert>#include<climits>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,n) for(int i=n;i;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define RepD(i,n) for(int i=n;i>=0;i--)#define MEM(a) memset(a,0,sizeof(a))#define MEMI(a) memset(a,127,sizeof(a))#define MEMi(a) memset(a,128,sizeof(a))#define INF (2139062143)#define F (1000000009)#define MAXN (1000+10)#define MAXM (1000+10)typedef long long ll;int T,n,P,p[MAXN],m,a[MAXN],s[MAXN],w[MAXN][MAXN],bin[MAXN],f[MAXN][MAXM];int main(){ freopen("CF-2013CTS01E04-challenge.in","r",stdin); cin>>T; bin[1]=1;Fork(i,2,30) bin[i]=bin[i-1]<<1;// For(i,30) cout<<bin[i]<<' '; while(T--) { cin>>n>>P;m=0; int P2=P; Fork(i,2,sqrt(P)) if (P%i==0) { P/=i; p[++m]=i; } if (P) p[++m]=P; P=P2; s[0]=0; For(i,n) cin>>a[i],s[i]=s[i-1]+a[i]; //For(i,m) cout<<p[i]<<' ';cout<<endl;// memset(w,0,sizeof(w)); For(i,n) Fork(j,i,n) { w[i][j]=0; int t=s[j]-s[i-1]; For(k,m) if (t%p[k]==0) w[i][j]|=bin[k]; } MEMI(f); // cout<<w[2][2]<<endl; For(i,n) Rep(j,bin[m+1]) { if ((w[1][i]&j)==j) f[i][j]=min(f[i][j],0); Fork(k,i+1,n) { f[k][w[i+1][k]|j]=min(f[k][w[i+1][k]|j],f[i][j]+1); } } int ans=1,mincut=0; Rep(i,bin[m+1]) { int t=1; For(k,m) if (bin[k]&i) t*=p[k]; if (t>ans&&f[n][i]^INF) { ans=t;mincut=f[n][i]; } } cout<<ans<<' '<<mincut<<endl; } while(1); return 0;}