Problem Link:
Difficulty:
Hard
Pre-Requisites:
dynamic-programming, inclusion-exclusion, combinatorics, bipartite-graphsProblem:
Given 3 * N matrix, whose first two rows are filled with permutations of [1…N], and third row is empty, find the number of ways of filling the third row such that each number(between 1 to N) appears at most once in each row and each column. The part of matrix already filled satisfies this property.
Explaination:
The current problem can be translated to finding the number of perfect matchings in a given (N-2)-regular N*N bipartite graph.
The vertices on left hand side of bipartite-graph represent positions in the third row. The vertices on the right hand side represent colors that can be filled into some position. The edges are assignments compatible with the first two rows (i.e. if first row is array A[i] and second row is array B[i], then there is an edge from i to all colors except A[i] and B[i]).
Coloring the third row of our matrix is equivalent to choosing exactly one edge(from the above graph G) incident to each position. The manner in which we have put edges ensure that C[i] ∉ {A[i], B[i]}. To make sure that C[i] ≠ C[j], the edges chosen should form a perfect matching.
Therefore, we need to find number of perfect matchings in a given (N-2)-regular bipartite graph G.
Let me define another related graph G’ which has same set of vertices as G, and all left to right edges that are not in G (i.e. vertex i on LHS has edge to vertices A[i] and B[i] on RHS).
The first step towards solution is realizing that the graph G’ has very simple structure. Every vertex has degree 2, so it is a union of disjoint cycles. If suppose we were asked to count number of matchings in G’, it would be far simpler. Given the size of all cycles of G’, the number of k-matchings can be found with a simple DP. Let Φ(k, G’) denote number of k-matchings in G’.
Let F(k) = The number of perfect matchings in G U G’ such that exactly k edges belong to G’ and N-k edges belong to G.
Any such matching consists of a k-matching in G’. So, can we use the value of Φ(k, G’) ?
The only problem in using Φ(k, G’) is that we dont know the number of ways to match the remaining vertices only using edges from G. To overcome this, we will consider all matchings of the remaining vertices in G U G’ (which is (N-k)! in number), and then remove those where more than k edges are used from G’.
Actual program for this is:F(k) = Φ(k, G’) * (N-k)! - F(k+1) * (k+1 choose k) - F(k+2) * (k+2 choose k) … - F(N) * (N choose k) --(1)
#include #include #include #includeusing namespace std;
#define MEM(a,b) memset(a,(b),sizeof(a))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))#define maxn 1000
#define maxt 10
#define M 1000000007#define MID 0
#define START 1
#define END 2typedef long long LL;
int A[1005],B[1005];
int posA[1005],posB[1005];
int n;
int seen[1005];
int type[1005];
int dp[1005];
int memo[1005][1005][2][2];
int ncr[1005][1005];
int fact[1005];void init()
{
int i,j;fact[0]=1; for(i=1;i<=maxn;i++) fact[i]=((LL)fact[i-1]*i)%M; for(i=0;i<=maxn;i++) ncr[i][0]=1; for(i=1;i<=maxn;i++) for(j=1;j<=i;j++) ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])%M;}
/*
pos = The current number
k = number of forbidden pairs remaining to match
a = true if the position at the right is matched with the previous number
b = true if the first number in the current cycle is placed at the last position
*/int solve(int pos,int k,int a,int b)
{
LL ret=0;if(pos==n) return (k==0); if(k<0 ) return 0; if(memo[pos][k][a][b]!=-1) return memo[pos][k][a][b]; if(type[pos]==START) { ret+=solve(pos+1,k-1,0,1); ret+=solve(pos+1,k-1,1,0); ret+=solve(pos+1,k,0,0); } if(type[pos]==END ) { if(!a) ret+=solve(pos+1,k-1,0,0); if(!b) ret+=solve(pos+1,k-1,0,0); ret+=solve(pos+1,k,0,0); } if(type[pos]==MID) { if(!a) ret+=solve(pos+1,k-1,0,b); ret+=solve(pos+1,k-1,1,b); ret+=solve(pos+1,k,0,b); } while(ret>=M) ret-=M; return memo[pos][k][a][b]=ret;}
int main()
{
int i,j,k,T,cs=0;init(); scanf("%d",&T); assert(T>=1 && T<=maxt); while(T--) { MEM(seen,0); MEM(type,0); MEM(memo,-1); scanf("%d",&n); assert(n>=3 && n<=maxn); for(i=0;i<n;i++) scanf("%d",&A[i]); for(i=0;i<n;i++) scanf("%d",&B[i]); MEM(posA,-1);MEM(posB,-1); for(i=0;i<n;i++) { assert(A[i]!=B[i]); assert(A[i]>=1 && A[i]<=n && posA[A[i]-1]==-1); assert(B[i]>=1 && B[i]<=n && posB[B[i]-1]==-1); --A[i];--B[i]; posA[A[i]]=i; posB[B[i]]=i; } // Finds the permutation cycles and places the numbers of the same cycle consecutively int cnt=0; for(i=0;i<n;i++) { if(seen[i]) continue; int u=i; type[cnt]=START; while(1) { cnt++; int x= B[posA[u]]; u=B[posA[u]]; if(u==i) break; seen[u]=1; } type[cnt-1]=END; } /* Number of ways k distinct forbidden number-position pairs can be chosen And use inclusion-exclusion principle to compute the number of permutations with exactly 0 forbidden positions */ for(k=n;k>=0;k--) { LL q=solve(0,k,0,0); q=(q*fact[n-k])%M; for(i=k+1;i<=n;i++) q=(q-((LL)ncr[i][k]*dp[i])%M)%M; dp[k]=q; } printf("%d\n",(dp[0]+M)%M); } return 0;}