B. Emordnilap【Codeforces Round #845 (Div. 2) and ByteRace 2023】

2023-01-22 11:58:40 来源：博客园

B. Emordnilap

原题链接A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array). There are n!=n⋅(n−1)⋅(n−2)⋅…⋅1 different permutations of length n.

Given a permutation p of n numbers, we create an array a consisting of 2n numbers, which is equal to p concatenated with its reverse. We then define the beauty of p as the number of inversions【颠倒】in a.

The number of inversions in the array a is the number of pairs of indices i, j such that iaj.

【资料图】

For example, for permutation p=[1,2], a would be [1,2,2,1]. The inversions in a are (2,4) and (3,4) (assuming 1-based indexing). Hence, the beauty of p is 2.

Your task is to find the sum of beauties of all n! permutations of size n. Print the remainder we get when dividing this value by 1000000007 (109+7).

InputEach test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105). The description of the test cases follows.

Each test case has only one line — the integer n (1≤n≤105).

It is guaranteed that the sum of n over all test cases does not exceed 105.

OutputFor each test case, print one integer — the sum of beauties of all permutations of size n modulo 1000000007 (109+7).

Exampleinput312100output04389456655NoteFor the first test case of the example, p=[1] is the only permutation. a=[1,1] has 0 inversions.

For the second test case of the example, the permutations are [1,2] and [2,1]. Their respective a arrays are [1,2,2,1] and [2,1,1,2], both of which have 2 inversions.

题意

给出一个n，求长度为n的排列经过反转拼接后得到的数组中颠倒的数目，求出n!种排列的情况得到的总和取模1000000007的值

思路

无论是哪一种排列情况颠倒数目都是相同的(\(n*(n-1)\))因此无论怎么排列，每两个不同的数\(i，j\)总会是\(2\)的颠倒贡献值\(2*\frac{n*(n-1)}{2} = n*(n-1)\)

为什么？我们可以只看排列中的两个元素，假设\(i j_{reverse}\)即\(i p_j\)，得到贡献为2因此无论怎么排列，每两个不同的数\(i，j\)总会是\(2\)的颠倒贡献值

总共有n!中排列情况
原题答案为\(n!*n*(n+1) mod 1000000007\)

代码

点击查看代码

#include#include#include#include#include#include#includeusing namespace std;#define X first#define Y secondtypedef long long LL;const char nl = "\n";const int N = 1e6+10;LL n;//int a[N];int cnt[N];int p = 1e9+7;void solve(){cin >> n;LL res = n*(n-1)%p;if(n == 1)cout << 0 << nl;else{for(int i = 1; i <= n; i ++){res *= i;res %= p;}//res *= res;res %= p;cout << res << nl;}}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T;cin >> T;while(T --){solve();}//solve();}

陌生单词

indices【下标】

关键词：点击查看