Author and Editorialist: Sahil Tiwari
Tester (C++): Abhishek Jugdar
Tester (Python): Aman Singhal

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:

1. Player whoâ€™s mannequin is selected by some other player hence this player can select any of the available mannequins.
2. 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.

1. 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]
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).

1. There are total (i+j)! permutations.
2. There are total ^jC_1 * (i+j-1)! permutations where at least one element is at restricted position.
3. 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))

3 Likes

Can somebody provide me with some good derangement problemsâ€™ link?

1 Like

Here you have considered situation W.R.T â€śjâ€ť and made two cases

and what about cases W.R.T â€śiâ€ť?

like if I am prioritising â€śiâ€ť case , there will be two cases like â†’

CASE1 â†’
any one of i is choosing mannequins from the ones that does not belong to any of the "j"s
then dp[i][j] = i x dp[i-1][j]
CASE2 â†’
anyone of i is choosing mannequins from the ones that belong to one of the "j"s
then dp[i][j] = j x dp[i-1 + 1][j-1] = j x dp[i][j-1]

CONCLUSION â†’
so basically dp[i][j] = (i x dp[i-1][j]) + (j x dp[i][j-1]) (I have checked that it works as an alternate solution Solution: 55348925 | CodeChef )

I am basically editing this comment! I got it now! Thanks for the wonderful problem man!

I am unable to understand why I am getting wrong answer can somebody help.