2022-9-1总结

A 传球

原题ARC124E

一个比较难的DP

首先可以发现必定有一个人没有传球，因为每个人都少传一个球的话状态不变。

然后考虑式子的实际含义，即为每个人在自己手中选一个球的方案数。

所以我们可以对着实际含义来做，每个人手上的球的来源只有原来没有传出去的球和上一个人传过来的球，所以我们可以将球的来源记录在DP状态里。

设 $f_{i,0}$ 表示第 $i-1$ 个人从自己手里选球时前 $i-1$ 个人的选球方案数， $f_{i,1}$ 表示第 $i$ 个人从传过来的球中选球时前 $i$ 个人的选球方案数。(将两个状态错开一个是为了方便转移)

转移就分 $4$ 中情况:

从 $f_{i,0}$ 转移到 $f_{i+1,0}$ : 自己和下一个人都不选被传的球，所以剩下几个球就有几种方案，方案数 $\sum\limits _{i=1}^{a_i} i$ 。
从 $f_{i,0}$ 转移到 $f_{i+1,1}$ : 有两个人没有计算，且都在 $a_i$ 中选球： $\sum\limits _{i=1}^{a_i-1} i(a_i-i)$
从 $f_{i,0}$ 转移到 $f_{i+1,0}$ : 需要计算 $a_i$ 中传出多少球，方案数 $a_i+1$
从 $f_{i,1}$ 转移到 $f_{i+1,1}$ : 和第一个类似，方案数 $\sum\limits _{i=1} ^{a_i} i$ 。

因为是一个环，需要DP一圈后统计 $1$ 处的答案，可以枚举 $1$ 的决策。(代码中由 A 实现 $1$ 的决策)

但是这样并没有保证传球数最小为 $0$ ，可以容斥一下，算出所有的再减去最小传球数为 $1$ 的就行了(代码中由 B 保证)

#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;

typedef long long ll;
const int N = 100005;
const int P = 998244353;

ll qpow(ll a, ll b);
ll s(ll x); ll g(ll x);


int n;
int a[N];
ll f[N][2];

ll inv2 = qpow(2, P-2);
ll inv6 = qpow(6, P-2);

ll calc(ll A, ll B);

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    a[n+1] = a[1];
    
    ll ans = calc(0,0)+calc(1,0)-calc(0,1)-calc(1,1);
    ans = (ans%P+P)%P;
    printf("%lld", ans);
}

ll calc(ll A, ll B)
{
    memset(f, 0, sizeof(f));
    f[1][0] = A;
    f[1][1] = A^1;
    for(int i = 1; i <= n; i++)
    {
        a[i] -= B;
        (f[i+1][0] += f[i][0]*s(a[i])%P) %= P;
        (f[i+1][0] += f[i][1]*(a[i]+1)%P) %= P;
    
        a[i] += B;
        (f[i+1][1] += f[i][0]*(a[i]*s(a[i])%P-g(a[i]))%P) %= P;
        (f[i+1][1] += f[i][1]*s(a[i])%P) %= P;
    }
    return f[n+1][A^1]; // 我这里直接把n+1处当作1了(这是个环)
}

ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}
ll s(ll x)
{
    return x * (x+1)%P *inv2%P;
}
ll g(ll x)
{
    return x * (x+1)%P * (2*x+1)%P * inv6%P;
}

C 龙与地下城

原题洛谷P8434

这是一道结论题：所有子串的装饰子集与原集合的装饰自己相同。

证明分两步：

原序列装饰子集的元素一定在子串的装饰子集中：对于一个元素 $a \in A$ ， $a$ 一定被划分在某个子串中，整个序列中没有二进制位包含 $a$ 的元素，子串中也不可能存在，所以 $a$ 一定属于它所在子串的装饰子集，而题目要求所有子串的装饰子集都相同，所以 $a$ 一定在所有子串的装饰子集中。
不在原序列装饰子集的元素一定不在子串的装饰子集中: 若 $a \not\in A$ ，则一定存在 $b \in A$ 使得 $a|b = b$ , 而 $b$ 一定在子串的装饰子集中，所以 $a$ 一定不在子串的装饰子集中。

所以我们可以先处理出原序列的装饰子集(dfs即可)，然后用双指针处理出在每一个右端点 $i$ 最近的 $l_i$ 使得 $[l_i,i]$ 包含整个装饰子集。

最后利用 $l_i$ 跑一个简单的DP即可解决，DP可以用前缀和优化。

#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;

typedef long long ll;
const int N = 3000005;
const int P = 1e9+7;

ll f[N];
int l[N];
int t[N];
int col[N];
bool vis[N];
int a[N], b[N];
int n, tot, cnt;

void dfs(int x);
void add(int x);
void del(int x);

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];


    stable_sort(b+1, b+n+1, [](int a, int b){
        return a > b;
    });

    for(int i = 1; i <= n; i++)
    {
        if(!vis[b[i]])
        {
            dfs(b[i]);
            col[b[i]] = ++tot;
        }
    }

    for(int lp = 1, rp = 1; rp <= n; rp++)
    {
        add(rp);
        while(lp <= rp and cnt == tot)
            del(lp++);
        l[rp] = lp-1;
    }

    f[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(l[i] != 0) f[i] = f[l[i]-1];
        (f[i] += f[i-1]) %= P;
    }
    ll ans = (f[n]-f[n-1]+P)%P;
    printf("%lld", ans);
}

void dfs(int x)
{
    if(vis[x]) return;
    vis[x] = true;
    for(int i = 1; i <= x; i <<= 1)
        if(x&i) dfs(x-i);
}

void add(int x)
{
    x = col[a[x]];
    if(x == 0) return;
    if(!t[x]) cnt++;
    t[x]++;
}
void del(int x)
{
    x = col[a[x]];
    if(x == 0) return;
    t[x]--;
    if(!t[x]) cnt--;
}