2022-07-27: Xiao Hong got an array arr with a length of N. she is going to modify it only once. She can modify any number arr[i] in the array to a positive number not greater than P (the modified numb

2022-07-27： Xiao Hong got a length of N Array of arr, She is going to make only one revision ,
Any number in the array can be arr[i], Change to no greater than P Positive number of （ The modified number must be different from the original number ),
And make the sum of all numbers X Multiple .
Xiao Hong wants to know , How many different modification schemes are there .
1 <= N, X <= 10^5.
1 <= arr[i], P <= 10^9.
From Netease .

answer 2022-07-27：

Find the cumulative sum of all numbers sum. Traverse ,sum-[i] Count times , Last count times .
The key to this problem lies in finding mathematical laws .
Time complexity ：O(N).

The code to use rust To write . The code is as follows ：

use rand::Rng;
fn main() {
    
    let len: i64 = 100;
    let value: i64 = 100;
    let test_time: i32 = 100000;
    println!(" Beginning of the test ");
    for _ in 0..test_time {
    
        let n = rand::thread_rng().gen_range(0, len) + 1;
        let mut arr = random_array(n, value);
        let p = rand::thread_rng().gen_range(0, value) + 1;
        let x = rand::thread_rng().gen_range(0, value) + 1;
        let ans1 = ways1(&mut arr, p, x);
        let ans2 = ways2(&mut arr, p, x);
        if ans1 != ans2 {
    
            println!(" Something went wrong !");
            break;
        }
    }
    println!(" End of test ");
}

fn ways1(arr: &mut Vec<i64>, p: i64, x: i64) -> i64 {
    
    let mut sum = 0;
    for num in arr.iter() {
    
        sum += *num;
    }
    let mut ans = 0;
    for num in arr.iter() {
    
        sum -= *num;
        for v in 1..=p {
    
            if v != *num {
    
                if (sum + v) % x == 0 {
    
                    ans += 1;
                }
            }
        }
        sum += num;
    }
    return ans;
}

fn ways2(arr: &mut Vec<i64>, p: i64, x: i64) -> i64 {
    
    let mut sum = 0;
    for num in arr.iter() {
    
        sum += *num;
    }
    let mut ans = 0;
    for num in arr.iter() {
    
        ans += cnt(p, x, *num, (x - ((sum - *num) % x)) % x);
    }
    return ans;
}

//  Current number num
// 1~p within , It can't be num Under the circumstances ,% x == mod How many numbers are there 
// O(1)
fn cnt(p: i64, x: i64, num: i64, mod0: i64) -> i64 {
    
    // p/x  At least a few 
    // (p % x) >= mod ? 1 : 0
    //  Without considering the number changed , Is it right? num Under the circumstances , Count the numbers , Meet the requirements 
    let ans = p / x + if (p % x) >= mod0 {
     1 } else {
     0 } - if mod0 == 0 {
     1 } else {
     0 };
    //  Can not be equal to num！
    return ans - if num <= p && num % x == mod0 {
     1 } else {
     0 };
}

//  In order to test 
fn random_array(n: i64, v: i64) -> Vec<i64> {
    
    let mut ans: Vec<i64> = vec![];
    for _ in 0..n {
    
        ans.push(rand::thread_rng().gen_range(0, v) + 1);
    }
    return ans;
}

The results are as follows ：

---

Zuo Shen java Code