没忍住又打了，chinese场只写出来3题，不过写出来4题的也就21个？（狗头

A

A脑子卡了一下，你想，1234有3个pi[HTML_REMOVED]pi+1的数量，它是对称的。
所以4个数的全排列的个数是4！，合法的就有4！/2个，但是这个计算取模就有点麻烦，推了好久，具体看代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 2e5 + 10, MOD = 1e9 + 7;
ll n;
ll jc[N];

int main()
{
    int t;
    cin >> t;

    jc[1] = 1;
    for(int i = 2; i <= 2e5; i ++) jc[i] = (jc[i - 1] * i) % MOD;

    while(t --)
    {
        cin >> n;
        cout << jc[2 * n - 1] * n % MOD << endl;
    }
}

B

B就是你去试试能不能构建一个图满足它的条件，首先要是连通图，边的上下界就出来了。
然后如果边数满足的话，我们首先用第一个点连接所有的点，这样可以保证树的直径不大于2，如果边数够用，我们把它们全部连起来，那么直径就是1了，再加个点数为1的特判即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 2e5 + 10, MOD = 1e9 + 7;
ll n, m, k;
ll jc[N];

int main()
{
    int t;
    cin >> t;

    while(t --)
    {
        cin >> n >> m >> k;
        k --;
        if(m >= n - 1 && m <= (n - 1) * n / 2)
        {
            int d;
            if(n == 1) d = 0;
            else if(m == (n - 1) * n / 2) d = 1;
            else d = 2;
            if(d < k) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else cout << "NO" << endl;
    }
}

C

C我的思路就是暴力加剪枝，不过这个剪枝挺重要的
首先求二维前缀和，这样可以快速计算某区域1的个数

然后遍历每个点，以这个点为左上角的顶点向右下画矩形，符合条件的矩形都拿来考虑，但是时间复杂度太高了，我就加了个判断，当左上角为（x1,y1)右下为(x2,y2)时，y2向右划的过程中呢，矩形(x1,y1,x2,y2-1)中元素改变个数是固定的，只有右边界的改变数会变，我就判断，如果左边这个大矩形改变的数量都大于等于当前答案了，就不继续探索了。

归根结底还是暴力啦，只不过因为他要求最小矩形才5*4还不算顶点，也就是说改变量不超过16，所以这样剪枝效果很好，就出来了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m;

const int N = 500;
int g[N][N], s[N][N];
int r[N], c[N];

int res;

int cnt(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

bool test(int x1, int y1, int x2, int y2)
{
    int toone, tozero;
    toone = 2 * (y2 - y1 - 1) + 2 * (x2 - x1 - 1);
    toone -= cnt(x1 + 1, y2, x2 - 1, y2) + cnt(x2, y1 + 1, x2, y2 - 1)
            + cnt(x1 + 1, y1, x2 - 1, y1) + cnt(x1, y1 + 1, x1, y2 - 1);
    tozero = cnt(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    int r = tozero + toone;

    int testv = 2 * (y2 - y1 - 1) + x2 - x1 - 1
            - cnt(x2, y1 + 1, x2, y2 - 1) - cnt(x1, y1 + 1, x1, y2 - 1)
            - cnt(x1 + 1, y1, x2 - 1, y1) + tozero;
    if(testv > res) return false;

    res = min(r, res);
    return true;
}

int main()
{
    int t;
    cin >> t;

    while(t --)
    {
        memset(g, 0, sizeof g);
        memset(r, 0, sizeof r);
        memset(c, 0, sizeof c);
        memset(s, 0, sizeof s);
        res = 1e9;

        cin >> n >> m;
        for(int i = 1; i <= n; i ++) 
        {
            for(int j = 1; j <= m; j ++)
            {
                char cc;
                do {cin >> cc;}
                while(cc < '0' || cc > '1');
                g[i][j] = cc - '0';
                s[i][j] = g[i][j] + s[i - 1][j] + r[i];
                r[i] += g[i][j];
                c[j] += g[i][j];
            }
            getchar();
        }

        for(int i = 1; i + 4 <= n; i ++)
            for(int j = 1; j + 3 <= m; j ++)
                for(int u = i + 4; u <= n; u ++)
                {
                    bool flag = true;
                    for(int v = j + 3; flag && v <= m; v ++)
                        flag = test(i, j, u, v);
                }


        cout << res << endl;
    }
}