Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cf1391/

前言

补题。

C

对于每个 $i$，向它前面第一个 $j (p_j > p_i)$ 连边，向后面第一个 $j (p_j > p_i)$ 连边。
问对于长度为 $n$ 的排列，有多少种图中带环。
思考什么时候会出现环。发现只要存在 $i < j < k$，使得 $\min(a_i,a_k) > a_j$，即两数之间出现比两数最小值小的数，就会有环。
假设 $a_i < a_k$，如果有 $a_j < a_i$ 就有环，无环的条件就是 $a_j > a_i$，但如果 $a_j > a_i$ 那么 $k = j$，另一边同理。这说明无环时，每个数都只会与相邻的数连边。
这个限制相当强力，因此可以考虑计算无环的个数，用减法计算出有环的个数。
手玩一下，可以发现无环的情况总是单峰的，即一段单增一段单减。否则就会出现谷底，而导致谷底处小于两边最小值成环。
那么定义 $f(i)$ 为长度为 $i$ 时的无环方案数，$f(i) = f(i-1) \times 2$，具体推导：
对于长度为 $i$ 的某个无环排列，整体加一后，在两侧添加 $1$ 都能构成新的合法排列。例如 $1,2,3$ 变为 $2,3,4$ 后在两侧加 $1$，因为 $1$ 总是最小的，不会影响单峰性。
如果对整体平移的证明感到不够严谨的话，可以用添加 $i + 1$ 的证明方法。要维护单峰，$i + 1$ 只能添加在数值 $i$ 的前面或后面，放在前面则将 $i$ 作为下降的第一个数，放在后面则将 $i$ 作为上升的倒数第二个数。即两种方案。
最后答案就是 $n! – 2^{n-1}$。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e6 + 100;
const int mod = 1e9 + 7;
int n;
long long f[maxn],g;
int main()
{
    read(n);
    g = f[1] = 1;
    for (int i = 2; i <= n; ++i) f[i] = (f[i-1] * 2) % mod,g = (g * i) % mod;
    printf("%lld\n",(((g - f[n]) % mod) + mod) % mod);
    return 0;
}

B

每个点右方向，通向右方或下方的点，要求改变若干个点的方向，使得每点都能到达 $(n,m)$，求最少次数。
不妨从终点开始考虑，对于 $(n-1,m)$ 和 $(n,m-1)$ 来说，方向是唯一固定的，检查是否要更改即可，而对于 $(n-1,m-1)$，任意方向都是可行的。
同理，对于所有的 $(i,m)$ 与 $(n,j)$，都有唯一固定的方向。而其他的所有点，无论方向如何，最后都会走到边界上，因此无需考虑。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 110;
int T,n,m;
char s[maxn][maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n),read(m);
        for (int i = 1; i <= n; ++i) read(s[i] + 1);
        int ans = 0;
        for(int i = 1;i<m;++i) if(s[n][i] != 'R') ++ans;
        for(int i = 1;i<n;++i) if(s[i][m] != 'D') ++ans;
        printf("%d\n",ans);
    }
    return 0;
}

A

有一个性质： $p_j OR p_i > \max(p_j,p_i)$，所以直接 $1,2,3,4,\ldots,n$ 即可。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
int T,n;
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) printf("%d ",i);
        putchar('\n');
    }
    return 0;
}

D

一旦包含 $4 \times 4$ 的子矩阵，就一定无解。因为 $4 \times 4$ 的矩阵可拆分成四个 $2 \times 2$ 的矩阵，而四个奇数相加一定为偶数。
也就是说 $\min(n,m) < 4$，而且只需要考虑 $2 \times 2$ 的矩阵，因此可以动态规划。
若 $n < m$ 则交换 $n,m$，定义 $f(i,j)$ 为前 $i$ 行满足条件，最后一行状态为 $j$ 的最小花费，枚举当前状态转移即可。
复杂度大概是 $n \times 2^m \times 2^m$。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; c != '0' && c != '1'; c = nc());
    for (; c == '0' || c == '1'; c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e6 + 100;
int n,m;
char s[maxn];
int a[maxn];
int f[maxn][10],ok[10][10],num[10];
int main()
{
    read(n),read(m);
    if(std::min(n,m) > 3) 
    {
        puts("-1");
        return 0;
    }
    else if(std::min(n,m) == 1) 
    {
        puts("0");
        return 0;
    }
    if(n >= m)
    {
        for (int i = 1; i <= n; ++i)
        {
            read(s + 1);
            for (int j = 1; j <= m; ++j) a[i] = (a[i] << 1) + s[j] - '0';
        }
    }
    else
    {
        for (int i = 1; i <= n; ++i) 
        {
            read(s + 1);
            for (int j = 1; j <= m; ++j) a[j] = (a[j] << 1) + s[j] - '0';
        }
    }
    if(n < m) std::swap(n,m);
    int maxx = 1 << m;
    num[1] = 1;
    for (int i = 2; i < maxx; ++i) num[i] = num[i >> 1] + (i & 1);
    if(m == 3)
    {
        for (int i = 0; i < maxx; ++i)
            for (int j = 0; j < maxx; ++j)
            {
                int num1 = num[(i & 3)] + num[(j & 3)];
                int num2 = num[(i & 6)] + num[(j & 6)];
                if ((num1 & 1) && (num2 & 1)) ok[i][j] = 1;
            }
    }
    else if(m == 2)
    {
        for (int i = 0; i < maxx; ++i)
            for (int j = 0; j < maxx; ++j)
                if ((num[i] + num[j]) & 1) ok[i][j] = 1;
    }
    for (int i = 0; i < maxx; ++i) f[1][i] = num[i ^ a[1]];
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j < maxx; ++j) f[i][j] = 1 << 30;
        for (int j = 0; j < maxx; ++j)
        {
            for (int k = 0; k < maxx; ++k)
            {
                if (!ok[j][k]) continue;
                int x = num[k ^ a[i]];
                f[i][k] = std::min(f[i][k], f[i - 1][j] + x);
            }
        }
    }
    int ans = 1 << 30;
    for (int i = 0; i < maxx; ++i) ans = std::min(ans, f[n][i]);
    printf("%d\n", ans);
    return 0;
}