TopCoder SRM 568 Div1 500 EqualSums

这题可以说是花了一个多月才解决（雾
暑假的时候就很认真想过了，就是差了一步，昨天突然开窍。
emmm我真棒

我们发现题目的条件可以转化为对于任意 $a\left[i\right]\left[j\right]=a\left[i\right]\left[1\right]+a\left[1\right]\left[j\right]-a\left[1\right]\left[1\right](i\>1,j\>1)$a[i][j]=a[i][1]+a[1][j]−a[1][1](i>1,j>1)
有些 $a\left[i\right]\left[j\right]$a[i][j]是已知的，那么我们就可以得到一些条件形如 $a\left[i\right]\left[1\right]+a\left[1\right]\left[j\right]=a\left[i\right]\left[j\right]+a\left[1\right]\left[1\right]$a[i][1]+a[1][j]=a[i][j]+a[1][1]
但这样还不够，由于每个数都要 $\>=0$>=0，也就是说对任意 $i\>1,j\>1$i>1,j>1， $a\left[i\right]\left[1\right]+a\left[1\right]\left[j\right]\>=a\left[1\right]\left[1\right]$a[i][1]+a[1][j]>=a[1][1]
就相当于要 $min\left\{a\right[i\left]\right[1\left]\right\}+min\left\{a\right[1\left]\right[j\left]\right\}\>=a\left[1\right]\left[1\right],i\>1,j\>1$min{a[i][1]}+min{a[1][j]}>=a[1][1],i>1,j>1

于是我们就可以把所有 $a\left[i\right]\left[1\right]$a[i][1]和 $a\left[1\right]\left[j\right]$a[1][j]单独拿出来，设为 $c_1$c1​到 $c_{2n-2}$c2n−2​，若 $c_i+c_j=v$ci​+cj​=v就在 $i,j$i,j之间连一条权值为 $v$v的边。对于一个联通块，只要其中一个点的权值确定了，整个联通块的点就都确定了。于是，我们就暴枚联通块中的一个点，把整个联通块求出来。再用 $f\left[i\right]\left[j\right]\left[k\right]$f[i][j][k]，表示前 $i$i个联通块，在已经求出的点中， $min\left\{a\right[w\left]\right[1\left]\right\}=j$min{a[w][1]}=j且 $min\left\{a\right[1\left]\right[w\left]\right\}=k$min{a[1][w]}=k的方案数。滚动数组优化掉一维，最后统计时只要保证 $j+k\>=a\left[1\right]\left[1\right]$j+k>=a[1][1]就行了。

如果 $a\left[1\right]\left[1\right]$a[1][1]不知道的话，有两种办法。第一种是暴力枚举。第二种的话，我们可以发现交换任意两行或任意两列答案不变，就把一个知道的交换到 $a\left[1\right]\left[1\right]$a[1][1]就行了。

#include <bits/stdc++.h> #define fr(i,x,y) for(int i=x;i<=y;i++) using namespace std; const int N=51; const int M=N<<1; const int p=1e9+7; int n,a[N][N],x,m; int g[M][M]; int c[M]; int b[M],vis[M]; int f[2][20][20]; template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; } class EqualSums { public: int count( vector <string> board ) ; }; void Add(int &x,int y){ x+=y; while(x>=p) x-=p; } void init(){ memset(c,-1,sizeof c); fr(i,2,n) if (a[i][1]!=-1) c[i-1]=a[i][1]; fr(i,2,n) if (a[1][i]!=-1) c[i+n-2]=a[1][i]; } void visit(int x){ b[x]=1; for(int i=1;i<=m;i++) if (g[x][i]!=-1&&!b[i]) visit(i); } int dfs(int x){ vis[x]=1; if (c[x]<0) return 0; for(int i=1;i<=m;i++){ if (g[x][i]==-1) continue; if (vis[i]&&c[x]+c[i]!=g[x][i]) return 0; if (vis[i]) continue; if (c[i]!=-1&&c[x]+c[i]!=g[x][i]) return 0; c[i]=g[x][i]-c[x]; if (!dfs(i)) return 0; } return 1; } int EqualSums::count(vector <string> board) { n=board.size(); m=2*n-2; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if (board[i][j]=='-') a[i+1][j+1]=-1; else a[i+1][j+1]=board[i][j]-'0'; int q=1,w=1; fr(i,1,n) fr(j,1,n) if (a[i][j]!=-1){ q=i;w=j;break; } //fr(i,1,n) swap(a[1][i],a[q][i]); //fr(i,1,n) swap(a[i][1],a[i][w]); int z,y; if (a[1][1]==-1) z=0,y=18; else z=a[1][1],y=a[1][1]; int ans=0; for(x=z;x<=y;x++){ memset(g,-1,sizeof g); memset(c,-1,sizeof c); memset(f,0,sizeof f); memset(b,0,sizeof b); fr(i,2,n) fr(j,2,n) if (a[i][j]!=-1) g[i-1][j+n-2]=g[j+n-2][i-1]=a[i][j]+x; //cout<<x<<endl; //cout<<g[1][2]<<' '<<g[2][1]; init(); int cur=0; f[0][19][19]=1; //cout<<c[1]<<endl; for(int i=1;i<=m;i++) if (!b[i]){ init(); //cout<<c[1]<<endl; //printf("i=%d,c[i]=%d\n",i,c[i]); int zz,yy; if (c[i]!=-1) zz=yy=c[i]; else zz=0,yy=18; cur^=1; memset(f[cur],0,sizeof f[cur]); visit(i); fr(j,zz,yy){ init(); c[i]=j; memset(vis,0,sizeof vis); if (!dfs(i)) continue; //cout<<j<<endl; int mn1=19,mn2=19; for(int k=1;k<n;k++) if (c[k]>=0) mn1=min(mn1,c[k]); for(int k=n;k<=m;k++) if (c[k]>=0) mn2=min(mn2,c[k]); //printf("%d %d %d\n",j,mn1,mn2); for(int k=0;k<=19;k++) for(int l=0;l<=19;l++) if (f[cur^1][k][l]) Add(f[cur][min(mn1,k)][min(mn2,l)],f[cur^1][k][l]); } } fr(i,0,18) fr(j,0,18) if (i+j>=x) Add(ans,f[cur][i][j]); } return ans; }