Codeforces Round #745 (Div. 2)

A. CQXYM Count Permutations

思路:

答案是(2n)!/2,不知道啥原理,靠样例猜。

题目的描述是:

Codeforces Round #745 (Div. 2)

 

而这种情况答案是(2n)!/2,这占了全排列一半的情况,那么另一半的情况应该是

 Codeforces Round #745 (Div. 2)

 

即这种情况答案应该也是(2n)!/2

而这个题防止意外可以用快速模,但是最关键的点在于,这个除以二要怎么处理,如果把得出的答案最后除以二,是不行的,因为这个答案是你模完之后的答案。

我们可以这么做,就是遇到第一个偶数的时候先把答案除以二,或者直接循环从3开始,因为2除以二就是1,那直接从3开始也是一样的。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int>PII;

const int N = 200010;
const LL MOD = 1000000007;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        LL res = 1;
        for (int i = 3; i <= 2 * n; i++)
            res = (res % MOD * i % MOD) % MOD;

        printf("%lld\n", res);
    }
    return 0;
}

 

上一篇:Codeforces Round #745 (Div. 1) 1580F. Problems for Codeforces


下一篇:分布式事物SAGA