20230214 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

dp + 根号分治，最短路图 + 拓扑，区间dp，贪心 + 双端队列维护hash

# A. 偷税计划

一直没有意识到大于 1 的数个数小于等于 25 的性质，剩下的都是 1。

思考一个 $\text{dp}$ 来计算这个东西。

设 $dp_{m, i}$ 表示从 $2 \sim m$ 中选择了 $i$ 个数，使得这 $i$ 个数互质的方案数。

答案就是:

$ANS = \sum_{i = 0}^mdp_{m, i}\times \dbinom ni \times i!$

那么就产生了 3 种做法来计算这个 $dp_{m, i}$ ：

暴力打表，设 $f_{i, s}$ 表示考虑了前 $i$ 个数，当前质数状态是 $s$ 的方案数。空间可能比较大，但是没关系，本地能跑就行。
把第 $16 \sim 25$ 个质数单独考虑，因为它们只能是独自出现，不能再乘上其他质数了，这样质数状态只用开到 $2^{15}$ 。
根号分治，还是设 $f_{m, j, s}$ 表示从 $2 \sim m$ 中选了 $j$ 个数，质数状态为 $s$ 的方案数。

这里详细讲一下第三种做法。

我们把 $2, 3, 5, 7$ 看作小质数， $11$ 以后的看作大质数，这样一来一个数只会包含一个大质数和若干小质数。

所以我们状态只用记 $2^4$ ，转移就类似背包。

对于小质数：

$f_{i, j + 1, s | t} += f_{i - 1, j, s}$

对于大质数：

枚举大质数的倍数 $w(w \times pri \leq m)$ ，所有的这些数中只能出现一个，也是个 01 背包。

把 $w$ 包含的小质数压出来，转移跟上面一样。

具体看代码吧。

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int T, n, m;

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

int p[110], tot, vis[110];

inline void euler(int n){
    for(int i = 2; i <= n; ++i){
        if(!vis[i]) p[tot++] = i;
        for(int j = 0; j <= tot && i * p[j] <= n; ++j){
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

int fac[N], ifac[N];

inline int qpow(int a, int b){
    int res = 1;
    for(; b; b >>= 1, a = mul(a, a))
        if(b & 1) res = mul(res, a);
    return res;
}

inline void init(int n){
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    ifac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
}

inline int C(int n, int m){
    return mul(fac[n], mul(ifac[m], ifac[n - m]));
}

int f[110][20], g[110][20], dp[110][110];

inline void prework(int n){
    for(int M = 1; M <= n; ++M){
        memset(f, 0, sizeof(f)), f[0][0] = 1;
        for(int i = 2; i <= M; ++i){ //小质数
            int flag = 0, s = 0;
            for(int j = 4; j < tot; ++j)
                if(i % p[j] == 0) {flag = 1; break;}
            if(flag) continue;

            memcpy(g, f, sizeof(f));
            for(int j = 0; j < 4; ++j)
                if(i % p[j] == 0) s |= (1 << j);
            for(int j = 0; j <= M; ++j)
                for(int t = 0; t < 16; ++t)
                    if(!(s & t)) f[j + 1][s | t] = add(f[j + 1][s | t] + g[j][t]);
        }

        for(int i = 4; i < tot; ++i){ //大质数
            memcpy(g, f, sizeof(f));
            for(int w = 1; w * p[i] <= M; ++w){
                int s = 0;
                for(int j = 0; j < 4; ++j)
                    if(w % p[j] == 0) s |= (1 << j);
                for(int j = 0; j <= M; ++j)
                    for(int t = 0; t < 16; ++t)
                        if(!(s & t)) f[j + 1][s | t] = add(f[j + 1][s | t] + g[j][t]);
            }
        }
    
        for(int j = 0; j <= M; ++j)
            for(int t = 0; t < 16; ++t)
                dp[M][j] = add(dp[M][j] + f[j][t]);
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    euler(100), init(1e5), prework(100);
    cin >> T;
    while(T--){
        cin >> n >> m;
        int ans = 0;
        for(int i = 0; i <= min(n, m); ++i)
            ans = add(ans + mul(dp[m][i], mul(C(n, i), fac[i])));
        cout << ans << '\n';
    }
    return 0;
}

# B. NAJKRACI

原题。

把最短路图跑出来，是个 $\text{DAG}$ 。

然后一条边经过次数就是它上面能到达它的点的个数乘上它往下走能走到的点的个数。

正反两边拓扑就行，反向拓扑的实现可以在正向拓扑时记一个栈，然后依次弹出来。

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

const int N = 1e4;
const int mod = 1e9 + 7;
int n, m;
struct node{
    int u, v, w, nxt;
}e[N << 1];
int head[N], tot;

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline void add(int x, int y, int z){
    e[++tot] = (node){x, y, z, head[x]};
    head[x] = tot;
}

typedef pair<int, int> P;
priority_queue <P, vector<P>, greater<P> > q;
int dis[N];
bool vis[N];

inline void dij(int s){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    q.push(P(0, s)), dis[s] = 0;
    while(!q.empty()){
        int x = q.top().se; q.pop();
        if(vis[x]) continue; vis[x] = 1;
        for(int i = head[x]; i; i = e[i].nxt){
            int y = e[i].v;
            if(dis[y] > dis[x] + e[i].w)
                dis[y] = dis[x] + e[i].w, q.push(P(dis[y], y));
        }
    }
}

int c1[N], c2[N], ans[N << 1];
vector <int> G[N];
int stk[N], in[N];

inline void topo(int s){
    memset(c1, 0, sizeof(c1));
    memset(c2, 0, sizeof(c2));
    queue <int> q;
    int top = 0;
    q.push(s), c1[s] = 1;
    while(!q.empty()){
        int x = q.front(); q.pop();
        stk[++top] = x;
        for(auto y : G[x]){
            c1[y] = add(c1[y] + c1[x]);
            if(!(--in[y])) q.push(y);
        }
    }
    while(top){
        int x = stk[top--]; c2[x]++;
        for(auto y : G[x]) c2[x] = add(c2[x] + c2[y]);
    }
}


inline void solve(int s){
    dij(s);
    for(int i = 1; i <= n; ++i) G[i].clear();
    for(int i = 1; i <= m; ++i)
        if(dis[e[i].v] == dis[e[i].u] + e[i].w){
            G[e[i].u].pb(e[i].v), in[e[i].v]++;
        }
    topo(s);
    for(int i = 1; i <= m; ++i)
        if(dis[e[i].v] == dis[e[i].u] + e[i].w)
            ans[i] = add(ans[i] + mul(c1[e[i].u], c2[e[i].v]));
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v, w; cin >> u >> v >> w;
        add(u, v, w);
    }
    for(int i = 1; i <= n; ++i) solve(i);
    for(int i = 1; i <= m; ++i) cout << ans[i] << '\n';
    return 0;
}

# C. Go

简单区间 dp.

套路的设 $f_{i, j, 0/1}$ 表示走过了 $i \sim j$ 之间的所有点且当前在最左/右的最大收益，同时记录一个 $g_{i, j, 0/1}$ 记需要的时间。

写的时候可以把所有坐标都转化成关键点，这样可能好写一点。

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1010;
int n, k, m;
int f[N][N][2], g[N][N][2];
int a[N], b[N], t[N];

inline bool chk(int f1, int f2, int g1, int g2){
    return f1 < f2 || (f1 == f2 && g1 > g2);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> k >> m;
    for(int i = 1; i <= n; ++i) t[i] = 1e9;
    for(int i = 1; i <= m; ++i){
        int x, v, w; cin >> x >> v >> w;
        b[x] = v, t[x] = w;
    }
    memset(f, -0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    f[k][k][0] = f[k][k][1] = b[k];
    g[k][k][0] = g[k][k][1] = 1;
    for(int len = 2; len <= n; ++len){
        for(int i = max(1, k + 1 - len); i <= k && i + len - 1 <= n; ++i){
            int j = i + len - 1, val;
            if(t[i] >= g[i + 1][j][0] + 1) val = b[i];
            else val = 0;
            if(chk(f[i][j][0], f[i + 1][j][0] + val, g[i][j][0], g[i + 1][j][0] + 1))
                f[i][j][0] = f[i + 1][j][0] + val, g[i][j][0] = g[i + 1][j][0] + 1;

            if(t[i] >= g[i + 1][j][1] + (j - i)) val = b[i];
            else val = 0;
            if(chk(f[i][j][0], f[i + 1][j][1] + val, g[i][j][0], g[i + 1][j][1] + j - i))
                f[i][j][0] = f[i + 1][j][1] + val, g[i][j][0] = g[i + 1][j][1] + j - i;
            
            if(t[j] >= g[i][j - 1][1] + 1) val = b[j];
            else val = 0;
            if(chk(f[i][j][1], f[i][j - 1][1] + val, g[i][j][1], g[i][j - 1][1] + 1))
                f[i][j][1] = f[i][j - 1][1] + val, g[i][j][1] = g[i][j - 1][1] + 1;
            
            if(t[j] >= g[i][j - 1][0] + j - i) val = b[j];
            else val = 0;
            if(chk(f[i][j][1], f[i][j - 1][0] + val, g[i][j][1], g[i][j - 1][0] + j - i))
                f[i][j][1] = f[i][j - 1][0] + val, g[i][j][1] = g[i][j - 1][0] + j - i;
        }
    }
    cout << max(f[1][n][0], f[1][n][1]) << '\n';
    return 0;
}

# D. 基因进化

假设要翻转两个前缀分别是 $i, j(j < i)$ 。

那么 $i$ 的翻转是不影响 $1 \sim j$ 的，也就是 $1 \sim j$ 一定能取到最小字典序的情况。

所以我们开一个双端队列就记当前已经考虑过的位置的最小字典序串是什么样的。

加进来一个新串有两种情况：

正序插到队列后面。
倒序插到队列前面（注意这里原答案串是不需要翻转的，因为当前字典序是最小的，且也可以表示出来）

插进来后二分 + Hash 把字典序小的留下来，大的删掉。

实现就是要动态维护 Hash。

#include <bits/stdc++.h>
#define pb push_back
#define ull unsigned long long

using namespace std;

const int N = 3e5 + 10;
const int mod = 998244353;
const int Bas = 1331;
int T, n, m;
int a[N], b[N], vis[N];
ull hx[N << 1], sum[N << 1];
int deq[N << 1];
int L, R;

inline void pushbk(int x) {deq[++R] = x, sum[R] = (sum[R - 1] + hx[R] * x);}
inline void pushfr(int x) {deq[--L] = x, sum[L - 1] = (sum[L] - hx[L] * x);}

inline bool chk(int L, int R, int len){
    int l = 0, r = len - 1, pos = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if((sum[L + mid - 1] - sum[L - 1]) * hx[R - L] == (sum[R + mid - 1] - sum[R - 1])) l = mid + 1, pos = mid;
        else r = mid - 1;
    }
    pos++;
    if(pos == len || deq[L + pos - 1] < deq[R + pos - 1]) return 1;
    return 0;
}

inline void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) vis[i] = 0;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1, x; i <= m; ++i) cin >> x, vis[x] = 1;
    L = N, R = N - 1;
    int lst = 1;
    for(int i = 1; i <= n; ++i){
        if(vis[i]) continue;
        int cnt = i - lst + 1;
        int r = L, len = R - L + 1;
        for(int j = lst; j <= i; ++j) pushbk(a[j]), pushfr(a[j]);
        int l = L;
        if(chk(l, r, len + cnt)) R -= cnt;
        else L += cnt;
        lst = i + 1;
    }
    for(int i = lst; i <= n; ++i) pushbk(a[i]);
    int ans = 0, tmp = 1;
    for(int i = L; i <= R; ++i)
        ans = (1ll * ans + 1ll * tmp * deq[i] % mod) % mod, tmp = tmp * 37ll % mod;
    cout << ans << '\n';
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    hx[0] = 1;
    for(int i = 1; i <= 6e5 + 10; ++i) hx[i] = hx[i - 1] * Bas;
    cin >> T;
    while(T--) solve();
    return 0;
}

# A. 偷税计划

# B. NAJKRACI

# C. Go

# D. 基因进化

20230212

20230215