1569c - July meeting (source address from ⇔CF1569C)

tag

⇔ number theory, ⇔ permutation and combination, ⇔ advanced (* 1500)

meaning of the title

There are \ (n \) individuals sitting in a circle to exchange proposals. The number of proposals of each person is given through the \ (a[1...n] \) array. Everyone will speak in order. The number of proposals made by the person who speaks once will be \ (- 1 \). When the number of proposals made by the person is \ (0 \), he will withdraw from the discussion. Now, how many possible permutations are there so that everyone can cross speak without a person speaking twice in a row.

thinking

Let's assume that the maximum number of proposals is \ (x \), and the number of proposals by a total of \ (X = Num_x \) individuals is \ (x \). By observing the examples and making a simple derivation, we find that the arrangement method is directly related to the number of \ (x \) - when \ (X \ge 2 \), no matter how the arrangement meets the requirements; When \ (X = 1 \), at least one person with \ (x-1 \) proposals must speak after this person's speaking order and before the next round. It may be assumed that there are \ (Y \) people with the second largest value \ (y = x - 1 \). So far, the topic is divided into three situations:

• \(x > 1 \), the answer is \ (A_n^n \);
• \(X = 1 \), and \ (Y = 0 \), the answer is \ (0 \);
• \(X = 1 \), and \ (Y \ne 0 \), discussed below.

Positive (own practice)

Arrange the next largest value (\ (a {y} ^ {y} \), the unique maximum value (\ (a 1 ^ 1 \)) can be inserted into any bit except the last bit (\ (C {y} ^ 1 \), and other numbers (\ (a {n - Y - 1} ^ {n - Y - 1} \)) can be inserted into any bit (ball box model, the ball is different from the box and can be empty, \ (C {(n - Y - 1) + (y + 1 + 1) - 1} ^ {(y + 1) - 1} = C_ {n}^{Y}\)).

So far, the answer is \ (Y! * y * (n - Y - 1)* C_ {n} ^ {y} \), further reduced to \ (n! - \ frac {n!} {Y + 1}\).

Reverse answer (practice)

First, consider the situation that does not meet the requirements: the person with the number of proposals \ (x \) is the last to speak. First arrange the next largest value (\ (a {y} ^ {y} \), insert the unique maximum value (\ (a 1 ^ 1 \)) into the last digit (\ (C 1 ^ 1 \), and then arrange other numbers (\ (a {n} ^ {n - Y - 1} \).

So far, the answer is \ (n! - a {n} ^ {n - Y - 1} * y! \), which is further simplified to \ (n! - \ frac {n!} {Y + 1}\) .

AC code 1 (use \ (\ tt{}vector \))

Click to view the code

void Solve() {
    int frac = 1, sub = 1;
    cin >> n;
    VI v(n);
    for(auto &it : v) cin >> it;
    
    int x = *max_element(v.begin(), v.end());
    int X = count(v.begin(), v.end(), x);
    int Y = count(v.begin(), v.end(), x - 1);
    
    FOR(i, 1, n) {
        frac = frac * i % MOD;
        if(i != Y + 1) sub = sub * i % MOD;
    }
    
    if(X == 1) frac = (frac - sub + MOD) % MOD;
    cout << frac << endl;
}

AC code 2 (hard calculation)

Click to view the code

LL C(LL n, LL m, LL p = MOD) {
    if(m > n) return 0;
    LL a = 1, b = 1;
    FOR(i, 1, m) {
        a = a * (n + i - m) % p;
        b = b * i % p;
    }
    return a * mypow(b, p - 2, p) % p;
}
LL Lucas(LL n, LL m, LL p = MOD) {//Lucas theorem
    LL ans = 1;
    while(n && m) {
        ans = ans * C(n % p, m % p, p) % p;
        n /= p;
        m /= p;
    }
    return ans;
}
void Prepare(int x) {
	FOR(i, 1, x) {
		A[i] = A[i - 1] * i % MOD;
	}
}
void Solve() {
	cin >> n;
	Prepare(n + 1);
	FOR(i, 1, n) cin >> a[i];
	
	sort(a + 1, a + 1 + n, [] (int x, int y) {
		return x > y;
	});
	mm = a[1];//Maximum
	nummm = 0;
	mn = 0;//Second largest value
	nummn = 1;
	FOR(i, 1, n) {
		if(a[i] == mm) nummm ++;
		else if(mn == 0) mn = a[i];
		else if(a[i] == mn) nummn ++;
		else break;
	}
	
	if(nummn != 0 && nummm == 1 && mm - mn != 1) { //The difference can only be 1
		ans = 0;
	}else if(nummm != 1) { //There is more than one maximum value, which is arranged randomly
		ans = A[n];
	}else if(nummm == 1) { //There is only one maximum
		//Number of boxes nummm + nummn + 1, number of balls n - nummm - nummn.
		ans = A[nummn] * nummn % MOD * Lucas(n, 1 + nummn) % MOD * A[n - 1 - nummn] % MOD;
	}
	cout << ans << endl;
}

Number of errors

nothing

Text / WIDA
Written on January 15, 2022
It was launched in WIDA personal blog for learning and discussion only

Update Journal:
Written on January 15, 2022