| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
Hard |
2644 |
Weekly Contest 374 Q4 |
|
You are given an integer n and an array sick sorted in increasing order, representing positions of infected people in a line of n people.
At each step, one uninfected person adjacent to an infected person gets infected. This process continues until everyone is infected.
An infection sequence is the order in which uninfected people become infected, excluding those initially infected.
Return the number of different infection sequences possible, modulo 109+7.
Example 1:
Input: n = 5, sick = [0,4]
Output: 4
Explanation:
There is a total of 6 different sequences overall.
- Valid infection sequences are
[1,2,3],[1,3,2],[3,2,1]and[3,1,2]. [2,3,1]and[2,1,3]are not valid infection sequences because the person at index 2 cannot be infected at the first step.
Example 2:
Input: n = 4, sick = [1]
Output: 3
Explanation:
There is a total of 6 different sequences overall.
- Valid infection sequences are
[0,2,3],[2,0,3]and[2,3,0]. [3,2,0],[3,0,2], and[0,3,2]are not valid infection sequences because the infection starts at the person at index 1, then the order of infection is 2, then 3, and hence 3 cannot be infected earlier than 2.
Constraints:
2 <= n <= 1051 <= sick.length <= n - 10 <= sick[i] <= n - 1sickis sorted in increasing order.
According to the problem description, the children who have a cold have divided the children who have not yet caught a cold into several continuous segments. We can use an array
Assuming that there is only one transmission scheme for each segment of children who are not cold, there are
Next, we consider the transmission scheme of each segment of children who are not cold. Suppose there are
In summary, the total number of cold sequences is:
Finally, we need to consider that the answer may be very large and need to be modulo
The time complexity is
mod = 10**9 + 7
mx = 10**5
fac = [1] * (mx + 1)
for i in range(2, mx + 1):
fac[i] = fac[i - 1] * i % mod
class Solution:
def numberOfSequence(self, n: int, sick: List[int]) -> int:
nums = [b - a - 1 for a, b in pairwise([-1] + sick + [n])]
ans = 1
s = sum(nums)
ans = fac[s]
for x in nums:
if x:
ans = ans * pow(fac[x], mod - 2, mod) % mod
for x in nums[1:-1]:
if x > 1:
ans = ans * pow(2, x - 1, mod) % mod
return ansclass Solution {
private static final int MOD = (int) (1e9 + 7);
private static final int MX = 100000;
private static final int[] FAC = new int[MX + 1];
static {
FAC[0] = 1;
for (int i = 1; i <= MX; i++) {
FAC[i] = (int) ((long) FAC[i - 1] * i % MOD);
}
}
public int numberOfSequence(int n, int[] sick) {
int m = sick.length;
int[] nums = new int[m + 1];
nums[0] = sick[0];
nums[m] = n - sick[m - 1] - 1;
for (int i = 1; i < m; i++) {
nums[i] = sick[i] - sick[i - 1] - 1;
}
int s = 0;
for (int x : nums) {
s += x;
}
int ans = FAC[s];
for (int x : nums) {
if (x > 0) {
ans = (int) ((long) ans * qpow(FAC[x], MOD - 2) % MOD);
}
}
for (int i = 1; i < nums.length - 1; ++i) {
if (nums[i] > 1) {
ans = (int) ((long) ans * qpow(2, nums[i] - 1) % MOD);
}
}
return ans;
}
private int qpow(long a, long n) {
long ans = 1;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
ans = ans * a % MOD;
}
a = a * a % MOD;
}
return (int) ans;
}
}const int MX = 1e5;
const int MOD = 1e9 + 7;
int fac[MX + 1];
auto init = [] {
fac[0] = 1;
for (int i = 1; i <= MX; ++i) {
fac[i] = 1LL * fac[i - 1] * i % MOD;
}
return 0;
}();
int qpow(long long a, long long n) {
long long ans = 1;
for (; n > 0; n >>= 1) {
if (n & 1) {
ans = (ans * a) % MOD;
}
a = (a * a) % MOD;
}
return ans;
}
class Solution {
public:
int numberOfSequence(int n, vector<int>& sick) {
int m = sick.size();
vector<int> nums(m + 1);
nums[0] = sick[0];
nums[m] = n - sick[m - 1] - 1;
for (int i = 1; i < m; i++) {
nums[i] = sick[i] - sick[i - 1] - 1;
}
int s = accumulate(nums.begin(), nums.end(), 0);
long long ans = fac[s];
for (int x : nums) {
if (x > 0) {
ans = ans * qpow(fac[x], MOD - 2) % MOD;
}
}
for (int i = 1; i < nums.size() - 1; ++i) {
if (nums[i] > 1) {
ans = ans * qpow(2, nums[i] - 1) % MOD;
}
}
return ans;
}
};const MX = 1e5
const MOD = 1e9 + 7
var fac [MX + 1]int
func init() {
fac[0] = 1
for i := 1; i <= MX; i++ {
fac[i] = fac[i-1] * i % MOD
}
}
func qpow(a, n int) int {
ans := 1
for n > 0 {
if n&1 == 1 {
ans = (ans * a) % MOD
}
a = (a * a) % MOD
n >>= 1
}
return ans
}
func numberOfSequence(n int, sick []int) int {
m := len(sick)
nums := make([]int, m+1)
nums[0] = sick[0]
nums[m] = n - sick[m-1] - 1
for i := 1; i < m; i++ {
nums[i] = sick[i] - sick[i-1] - 1
}
s := 0
for _, x := range nums {
s += x
}
ans := fac[s]
for _, x := range nums {
if x > 0 {
ans = ans * qpow(fac[x], MOD-2) % MOD
}
}
for i := 1; i < len(nums)-1; i++ {
if nums[i] > 1 {
ans = ans * qpow(2, nums[i]-1) % MOD
}
}
return ans
}const MX = 1e5;
const MOD: bigint = BigInt(1e9 + 7);
const fac: bigint[] = Array(MX + 1);
const init = (() => {
fac[0] = 1n;
for (let i = 1; i <= MX; ++i) {
fac[i] = (fac[i - 1] * BigInt(i)) % MOD;
}
return 0;
})();
function qpow(a: bigint, n: number): bigint {
let ans = 1n;
for (; n > 0; n >>= 1) {
if (n & 1) {
ans = (ans * a) % MOD;
}
a = (a * a) % MOD;
}
return ans;
}
function numberOfSequence(n: number, sick: number[]): number {
const m = sick.length;
const nums: number[] = Array(m + 1);
nums[0] = sick[0];
nums[m] = n - sick[m - 1] - 1;
for (let i = 1; i < m; i++) {
nums[i] = sick[i] - sick[i - 1] - 1;
}
const s = nums.reduce((acc, x) => acc + x, 0);
let ans = fac[s];
for (let x of nums) {
if (x > 0) {
ans = (ans * qpow(fac[x], Number(MOD) - 2)) % MOD;
}
}
for (let i = 1; i < nums.length - 1; ++i) {
if (nums[i] > 1) {
ans = (ans * qpow(2n, nums[i] - 1)) % MOD;
}
}
return Number(ans);
}