不管怎么掰都是n*m-1
#include<cstdio> using namespace std; int main() { freopen("bpmp.in","r",stdin); freopen("bpmp.out","w",stdout); int n,m; scanf("%d%d",&n,&m); int ans=(1ll*n*m-1)%998244353; printf("%d",ans); }
将行状态压缩，枚举哪些行被折成了一条
枚举时，上一次选取的行 与 这一次选取的行 奇偶性不同，这两行才能折到一起
选取列也要求 上一个选的列与这一个选的列奇偶性不同
dp计算这一条上选哪些列
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,ans; int a[21][501],c[501]; int dp(int s) { bool f=false; memset(c,0,sizeof(c)); for(int i=0;i<n;i++) if(s&(1<<i)) for(int j=0;j<m;j++) c[j]+=a[i][j]; for(int j=0;j<m;j++) if(c[j]>0) { f=true; break; } if(!f) return -2e9; int c0=0,c1=0,x; for(int i=0;i<m;i++) if(i&1) c1=max(c[i]+c0,c1); else c0=max(c[i]+c1,c0); return max(c1,c0); } void dfs(int now,int last,int state) { if(now==n) { ans=max(ans,dp(state)); return; } if(last==-1 || ((now-last)&1)) dfs(now+1,now,state|(1<<now)); dfs(now+1,last,state); } int main() { freopen("cfyw.in","r",stdin); freopen("cfyw.out","w",stdout); scanf("%d%d",&n,&m); ans=-2e9; for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&a[i][j]),ans=max(ans,a[i][j]); if(ans>0) dfs(0,-1,0); printf("%d",ans); }
推公式+除法分块
http://www.cnblogs.com/TheRoadToTheGold/p/6696450.html
#include<cstdio> #include<algorithm> #define N 10000001 #define mod 998244353 using namespace std; int p[1000001],phi[N],cnt; long long sum[N]; bool vis[N]; void pre(int n) { phi[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) { vis[i]=true; phi[i]=i-1; p[++cnt]=i; } for(int j=1;j<=cnt;j++) { if(i*p[j]>n) break; vis[i*p[j]]=true; if(i%p[j]==0) { phi[i*p[j]]=phi[i]*p[j]; break; } else phi[i*p[j]]=phi[i]*(p[j]-1); } } for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i]; } int main() { freopen("hoip.in","r",stdin); freopen("hoip.out","w",stdout); int n,m; scanf("%d%d",&n,&m); pre(min(n,m)); long long ans=0; long long j; for(long long i=1;i<=min(n,m);i=j+1) { j=min(n/(n/i),m/(m/i)); ans=(ans+(sum[j]-sum[i-1])*(n/i)%mod*(m/i)%mod)%mod; } printf("%I64d",ans); }