PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author and Editorialist: Sahil Tiwari
Tester (C++): Abhishek Jugdar
Tester (Python): Aman Singhal
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming , Combinatorics
PROBLEM:
Given an array A of size N, where elements are either unique or 0, find the number of ways to generate an array B such that if A_i \neq 0 then B_i = A_i and if A_i = 0 then B_i \neq i. Also B should contain all numbers from 1 to N.
EXPLANATION:
The question is basically a derangement problem. For any given array A, there are two types of undecided players:
- Player who’s mannequin is selected by some other player hence this player can select any of the available mannequins.
- Player who’s mannequins are still not selected and this player can select any mannequin except 1.
Let the number of type 1 players be i and the number of players of type 2 be j.
Answer to this parameter be dp[i][j].
Base Case:
dp[i][0] = factorial(i)
dp[0][j] = derangement(j)
Lets find ways such that j players find mannequins.
- The j^{th} player can select one of the j-1 players mannequins. Then i will increase by 1 since whoever amongst j-1 player’s mannequins was selected, becomes a type 1 player. Hence dp[i][j] = (j-1)*dp[i+1][j-2]
- The j^{th} player can select one of the i players mannequins. Hence dp[i][j] = i*dp[i][j-1]
We can precompute the answer for every pair of (i,j) and answer for every test case in linear time.
Time Complexity: O(max(N)^2 + \sum N )
ALTERNATE SOLUTION:
There exists an O(N) solution using the principle of Inclusion-Exclusion.
For the given pair of (i,j).
- There are total (i+j)! permutations.
- There are total ^jC_1 * (i+j-1)! permutations where at least one element is at restricted position.
- There are total ^jC_2 * (i+j-2)! permutations where at least two elements are at restricted position.
.
and so on…
This logic can be better understood by the derangement proof.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int N = 1000;
int der[N + 1] = {0};
map<int,int> f;
int mod = 1e9+7;
// function to precompute dearrangement
void countDer(int N)
{
der[1] = 0;
der[2] = 1;
for (int i = 3; i <= N; ++i)
der[i] = ((i - 1) * (der[i - 1] + der[i - 2])) % mod;
}
int fact(int n){
if(n<2)
return 1;
if(f.find(n) != f.end())
return f[n];
return f[n] = n*fact(n-1) % mod;
}
int dp[1001][1001];
signed main()
{
for(auto &i: dp)
for(auto &j: i)
j = 0;
countDer(N);
// i = free set
// j = restricting set
for(int i=1;i<=1000;i++){
dp[i][0] = fact(i);
dp[0][i] = der[i];
dp[i][1] = i*fact(i) % mod;
}
for(int j=2 ; j<=1000 ; j++){
for(int i=1000 ; i>0 ; i--){
if(i+j > 1000)
continue;
dp[i][j] = (dp[i][j] + i*dp[i][j-1] % mod) % mod;
dp[i][j] = (dp[i][j] + (j-1)*dp[i+1][j-2] % mod) % mod;
}
}
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> b(n);
for(int &i: b)
cin>>i;
map<int, int> c;
for (int i : b)
c[i]++;
int r = 0, k = 0;
for (int i = 1; i <= n; i++)
if (b[i - 1] == 0 && c[i] == 0)
r++;
else if (b[i - 1] == 0)
k++;
// r = restricted set
// k = non restricted set
cout<<dp[k][r]<<endl;
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Mint {
private:
const static int mod = 1e9 + 7;
int val;
public:
Mint () {val = 0;}
Mint(int _val) : val(_val) {}
Mint& operator += (const Mint &o) {val = (val + o.val < mod ? val + o.val : val + o.val - mod); return *this;}
template <typename T> Mint& operator += (const T &o) {return *this += Mint(o);}
Mint& operator -= (const Mint &o) {val = (val < o.val ? val - o.val + mod : val - o.val); return *this;}
template <typename T> Mint& operator -= (const T &o) {return *this -= Mint(o);}
Mint& operator *= (const Mint &o) {return *this = (1LL * val * o.val >= mod ? (1LL * val * o.val) % mod : val * o.val);}
template <typename T> Mint& operator *= (const T &o) {return *this *= Mint(o);}
friend bool operator == (const Mint &o1, const Mint &o2) {return (o1.val == o2.val);}
template <typename T> friend bool operator == (const Mint &o1, const T &o2) {return (o1 == Mint(o2));}
template <typename T> friend bool operator == (const T &o1, const Mint &o2) {return (Mint(o1) == o2);}
friend bool operator != (const Mint &o1, const Mint &o2) {return (o1.val != o2.val);}
template <typename T> friend bool operator != (const Mint &o1, const T &o2) {return (o1 != Mint(o2));}
template <typename T> friend bool operator != (const T &o1, const Mint &o2) {return (Mint(o1) != o2);}
friend Mint operator + (const Mint &o1, const Mint &o2) {return Mint(o1) += o2;}
template <typename T> friend Mint operator + (const Mint &o1, const T &o2) {return Mint(o1) += o2;}
template <typename T> friend Mint operator + (const T &o1, const Mint &o2) {return Mint(o1) += o2;}
friend Mint operator - (const Mint &o1, const Mint &o2) {return Mint(o1) -= o2;}
template <typename T> friend Mint operator - (const Mint &o1, const T &o2) {return Mint(o1) -= o2;}
template <typename T> friend Mint operator - (const T &o1, const Mint &o2) {return Mint(o1) -= o2;}
friend Mint operator * (const Mint &o1, const Mint &o2) {return Mint(o1) *= o2;}
template <typename T> friend Mint operator * (const Mint &o1, const T &o2) {return Mint(o1) *= o2;}
template <typename T> friend Mint operator * (const T &o1, const Mint &o2) {return Mint(o1) *= o2;}
Mint power(long long y) {
Mint ans = 1;
Mint x = *this;
while(y > 0) {
if(y & 1) ans *= x;
y >>= 1;
x *= x;
}
return ans;
}
Mint inverse () {return power(mod - 2);}
Mint& operator /= (const Mint &o) {return *this *= Mint(o).inverse();}
template <typename T> Mint& operator /= (const T &o) {return *this *= Mint(o).inverse();}
friend Mint operator / (const Mint &o1, const Mint &o2) {return Mint(o1) /= o2;}
template <typename T> friend Mint operator / (const Mint &o1, const T &o2) {return Mint(o1) /= o2;}
template <typename T> friend Mint operator / (const T &o1, const Mint &o2) {return Mint(o1) /= o2;}
bool operator ~ () const {return ~(this -> val);}
bool operator ! () const {return (this -> val == 0);}
void operator ++ () {*this += 1;}
void operator -- () {*this -= 1;}
void operator ++ (int) {*this += 1;}
void operator -- (int) {*this -= 1;}
friend ostream &operator << (ostream &os, const Mint &o) {os << o.val; return os;}
};
const int maxN = 1e3 + 5;
vector<Mint> fact(maxN), ivfact(maxN);
Mint nCr(int n, int r) {if(n < r || n < 0 || r < 0) return 0; return fact[n] * ivfact[r] * ivfact[n - r];}
void preprocess() {
fact[0] = ivfact[0] = 1;
for(int i = 1; i < maxN; i++) {
fact[i] = fact[i - 1] * i;
ivfact[i] = 1 / fact[i];
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
preprocess();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<bool> vis(n + 1, false);
for (int x : a) {
vis[x] = true;
}
int s1 = 0, s2 = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
if (a[i - 1] == 0) s1++;
else s2++;
}
int rem = s1 + s2;
if (rem == 0) {
cout << 0 << '\n';
continue;
}
Mint ans = fact[rem];
for (int i = 1; i <= s1; i++) {
Mint res = nCr(s1, i) * fact[rem - i];
if (i & 1) ans -= res;
else ans += res;
}
cout << ans << '\n';
}
}
Tester's Solution (Python)
N=1000
mod=(10**9)+7
fact=[1 for i in range(N+1)]
inv=[1 for i in range(N+1)]
val=1
for i in range(1,N+1):
val=(val*i)%mod
fact[i]=val
inv[i]=pow(fact[i],mod-2,mod)
def nCr(n,r):
return (fact[n]*inv[r]*inv[n-r])%mod
def solve(A):
n=len(A)
s1,s2=0,0
s=set(A)
for i in range(1,n+1):
if i not in s:
if (A[i-1]==0):
s1+=1
else:
s2+=1
rem=s1+s2
if (rem==0):
return 0
res=0
for i in range(1,s1+1):
if (i%2!=0):
res=(res+((nCr(s1,i)*fact[rem-i])%mod))%mod
else:
res=(res-((nCr(s1,i)*fact[rem-i])%mod))%mod
ans=(fact[rem]-res)%mod
return ans
T=int(input())
for _ in range(T):
n=int(input())
A=list(map(int,input().split()))
print(solve(A))
