SRM 568 Div1Med EqualsSum

問題

一部の成分が指定されているN*N行列が与えられる.
が一定で全ての成分が非負整数になるような割り当ての個数を1e+7で割った余りを求める.

解法

Editorial と違う解法で解いた.

のうち、3つが既知のとき、残りの1つも一意に定まるので、その成分をあらかじめ決定しておく.

列ベクトル を考えると は一定になっている.
行ベクトルに対しても同様なので, それらの列/行を消去して, 各列/行 には高々1つの成分が指定されていないように行列を変形できる.(全ての成分は0以上であり、小さい方のベクトルが本質なので, 小さい方のベクトルを残す)
また、1つの成分も指定されていない行があるとき, 解は無限大になるから各列/行は丁度1つの成分が指定されていることが言える.
(対角成分だけ指定されていて、他は指定されていない行列が得られる)

を基準にして, 列/行の差の最小値を状態としてもつDPをすると解が求まる.

コード

#define N 55
ll mod = 1000000007;
ll dp[N][30][30];
ll z[N];

class EqualSums {
public:
	int count( vector <string> g) {
		int n = g.size();
		vector<vector<int> > v(n, vector<int>(n, -1));
		rep(i, n) rep(j, n) if(g[i][j]!='-') v[i][j] = g[i][j]-'0';
		rep(_, n) rep(i, n) rep(j, n){
			if(v[i][j]<0) continue;
			rep(k, n) rep(l, n){
				if(v[k][l]<0) continue;
				int a = v[i][j]+v[k][l];
				if(v[i][l]>=0){
					int b = a-v[i][l];
					if(b<0 || v[k][j]>=0 && v[k][j]!=b) return 0;
					v[k][j] = b;
				} else if(v[k][j]>=0){
					int b = a-v[k][j];
					if(b<0 || v[i][l]>=0 && v[i][l]!=b) return 0;
					v[i][l] = b;
				}
			}
		}
		int m = n;
		rep(i, m) rep(j, i) rep(k, n){
			if(v[i][k]>=0 && v[j][k]>=0){
				if(v[i][k]<v[j][k]) swap(v[i], v[j]);
				swap(v[i], v[m-1]);
				m--;
				i--; j = n; break;
			}
		}
		int m2 = n;
		rep(i, m2) rep(j, i) rep(k, m){
			if(v[k][i]>=0 && v[k][j]>=0){
				if(v[k][i]<v[k][j]) rep(l, m) swap(v[l][i], v[l][j]);
				rep(l, m) swap(v[l][i], v[l][m2-1]);
				m2--;
				i--; j = n; break;
			}
		}
		n = m;
		rep(i, n){
			if(v[i][i]>=0) continue;
			for(ll j = i; j < n; j++) for(ll k = i; k < n; k++){
				if(v[j][k]>=0){
					if(i!=j) swap(v[i], v[j]);
					if(i!=k) for(ll l = i; l < n; l++) swap(v[l][i], v[l][k]);
					j = k = n; break;
				}
			}
		}
		int V = v[0][0];
		rep(i, n-1) z[i] = v[i+1][i+1]-V;
		mset(dp, 0);
		dp[0][0][0] = 1;
		rep(i, n-1){
			rep(j, V+1) rep(k, V+1){
				for(ll l = -V; z[i]-l >= -V; l++){
					(dp[i+1][max(j, -l)][max(k, -(z[i]-l))]+=dp[i][j][k])%=mod;
				}
			}
		}
		ll res = 0;
		rep(i, V+1) rep(j, i+1) (res+=dp[n-1][j][i-j])%=mod;
		return res;
	}
};