100 + 0 + 10 + 30, rk 70。

我不想玩啦！还是找个班上吧。

A

Subtask 1,2,3

直接按照题目里面给的做法，那么每一次都尝试把可以合并的元素合并，迭代若干次后如果没有修改，则说明无解。如果任意时刻只剩下一个元素，那么显然是合法的，直接用 long long 实现，可以得到 80 pts 的高分！

const int N = 1e5 + 10;
ll n;
vector <ll> a,b;
ll gcd(ll x,ll y) {return !y ? x : gcd(y,x % y);}
ll lcm(ll x,ll y) {return x / gcd(x,y) * y;}

signed main() {
    read(n);
    for (int i = 0,x;i < n;++i) read(x),a.emplace_back(x);
    bool flag = 0,cor = 0;
    while (1) {
        ll nowlcm = a[0];
        int le = a.size();
        b.clear();
        if (le == 1) {
            cor = 1;
            break;
        }
        bool tmp = 0;
        for (int i = 1;i < le;++i) {
            if (gcd(a[i],a[i-1]) != 1) {
                nowlcm = lcm(nowlcm,a[i]);
                tmp = 1;
            } else {
                b.emplace_back(nowlcm);
                nowlcm = a[i];
            }
        }
        b.emplace_back(nowlcm);
        if (!tmp) break;
        a = b;
    }
    if (cor) puts("Yes");
    else puts("No");
    return 0;
}

Subtask 4

我们考虑，上边的做法会在 a_i 过大时因为 lcm 爆炸寄掉，所以我们考虑直接模拟这个求 lcm 的过程。

我们发现，我们其实并不需要直接求出 lcm 的具体值，我们只需要在乎每个质数 p 是否能被取到而已。所以我们考虑用一个 bitset 来表示 p 的取值情况。那么我们判断 gcd > 1 只需要 (x & y).any(),求 lcm 只需要 x |= y 即可。

然后发现上边过程时间的正确性，其实是基于我们一共只需要扫描两次：第一次合并所有段，第二次考察是否有 lcm 存在。

所以我们可以直接用栈维护以上过程，时间复杂度 \mathcal{O}(n\times \frac{700}{64})

bool isprime(int x) {
    for (int i = 2;i * i <= x;++i) {
        if (x % i == 0) return 0;
    }
    return 1;
}

signed main() {
    //FO(ex_cai4)
    //freopen("ex_cai4.in","r",stdin);
    read(n);
    for (int i = 1,x;i <= n;++i) read(A[i]),maxx = max(maxx,A[i]);
    for (int i = 2;i <= maxx;++i) {
        int now = i;
        for (int j = 2;j * j <= i;++j) {
            if (!isprime(j)) continue;
            int cnt = 0;
            while (now % j == 0) {
                now /= j;
                ++cnt;
            }
            if (cnt) fac[i].set(j);
        }
        if (now != 1) fac[i].set(now);
    }
    for (int i = 1;i <= n;++i) {
        st[++top] = fac[A[i]];
        while (top > 1 && (st[top-1] & st[top]).any()) --top,st[top] |= st[top+1];
    }
    if (top == 1) puts("Yes");
    else puts("No");
    return 0;
}

B

场上弱智了完全没有想到分开来讨论……好好把一个弱智DP题做成逆天图论数数题。

首先最强的观察在于，我们考虑这个约束实际上具有一个非常强的暗示，我们可以把 U/D 和 L/R 分开来讨论，也就是说，我们对于每一行每一列分别考虑。

接下来叙述对于行的 DP 过程，对于列的 DP 过程也是同理。

我们首先发现这个问题有点类似一个括号匹配的过程，即 R 视为左括号，L 视为右括号，那么我们可以套路地定义出状态 f_{i,j} 表示考虑了前 i 个元素，有 j 个左括号尚未匹配的方案数。并且由于权值的存在，我们需要额外维护一个 g_{i,j} 表示对应的 f_{i,j} 情况的权值和。

接下来我们开始分类讨论：

• 如果当前为 L，那么括号数 -1，如果选择就是：

  f_{i,j-1} \leftarrow f_{i-1,j} \times j\\ g_{i,j-1} \leftarrow g_{i-1,j}\times j + f_{i-1,j}\times j\times a_i

  意义：对于方案数，考虑当前位置的可以和前 j 个左括号选择一个匹配；对于权值和，同样考虑有 j 个括号可供转移，并且加上当前的权值和(即 f_{i-1,j} \times j\times a_i)

• 如果当前为 R，那么括号数 +1，如果选择就是： f_{i,j-1} \leftarrow f_{i-1,j}\\ g_{i,j-1}\leftarrow g_{i-1,j} + f_{i-1,j}\times a_i

  类比上方，此处意义显然。

注意这两处都是只考虑了选择的，如果不选择，那么有

f_{i,j} \leftarrow f_{i-1,j}\\ g_{i,j} \leftarrow g_{i-1,j}

这个是显然的，转移的时候注意一下，总时间复杂度 \mathcal{O}(n^3)

const int N = 510;
char s[N][N];
int n,a[N][N],m,cnt[N * N],ans,f[N][N],g[N][N];

signed main() {
    scanf("%lld\n",&n);
    for (int i = 1;i <= n;++i) scanf("%s",s[i] + 1);
    for (int i = 1;i <= n;++i) 
        for (int j = 1;j <= n;++j) 
            scanf("%lld",&a[i][j]);

    ll tmp = 1,ans = 0;
    for (int x = 1;x <= n;++x) {
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        f[0][0] = 1;
        for (int i = 1;i <= n;++i) {
            for (int j = 0;j <= i;++j) {
                f[i][j] = f[i-1][j];
                g[i][j] = g[i-1][j];
                if (s[x][i] == 'U' || s[x][i] == 'D') continue;
                if (s[x][i] == 'L') {
                    f[i][j] = (f[i][j] + f[i-1][j+1] * (j + 1)) % mod;
                    g[i][j] = (g[i][j] + g[i-1][j+1] * (j+1) % mod + f[i-1][j+1] * (j+1) % mod * a[x][i] % mod) % mod;
                } else if (s[x][i] == 'R' && j > 0) {
                    f[i][j] = (f[i][j] + f[i-1][j-1]) % mod;
                    g[i][j] = (g[i][j] + g[i-1][j-1] + f[i-1][j-1] * a[x][i] % mod) % mod;
                }
            }
        }
        ans = (ans * f[n][0] % mod + tmp * g[n][0] % mod) % mod;
        tmp = (tmp * f[n][0]) % mod;
    }

    for (int x = 1;x <= n;++x) {
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        f[0][0] = 1;
        for (int i = 1;i <= n;++i) {
            for (int j = 0;j <= i;++j) {
                f[i][j] = f[i-1][j];
                g[i][j] = g[i-1][j];
                if (s[i][x] == 'L' || s[i][x] == 'R') continue;
                if (s[i][x] == 'U') {
                    f[i][j] = (f[i][j] + f[i-1][j+1] * (j + 1)) % mod;
                    g[i][j] = (g[i][j] + g[i-1][j+1] * (j+1) % mod + f[i-1][j+1] * (j+1) % mod * a[i][x] % mod) % mod;
                } else if (s[i][x] == 'D' && j > 0) {
                    f[i][j] = (f[i][j] + f[i-1][j-1]) % mod;
                    g[i][j] = (g[i][j] + g[i-1][j-1] + f[i-1][j-1] * a[i][x] % mod) % mod;
                } else {
                    continue;
                }
            }
        }
        ans = (ans * f[n][0] % mod + tmp * g[n][0] % mod) % mod;
        tmp = (tmp * f[n][0]) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}