考虑每一次投掷后的最坏结果，有几个人可能手里有球？

最坏时间复杂度是多少？能不能爆搜？

一个人可能有多个球的来源，需要去重。

纯纯广度优先暴力搜索，最坏时间复杂度，需要注意的是，爆搜时可能会有个数字在队列中，而人数最多一共才个人，证明必然有大量的重复，所以不可以用队列，而需要用集合来维护。

比赛当时，没注意队列可能的重复问题了不知道多少发……

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
const int maxn = 1010;
int n, m, x;
pair<char, int> rem[maxn];
void bfs()
{
    set<int> s;
    set<int>q;
    q.insert(x);
    for (int i = 1; i <= m; i++)
    {
        int j = q.size();
        char c = rem[i].first;
        int d = rem[i].second;
        for (auto top:q)
        {
            if (c == '0')
            {
                int nxt = (top + d) % n;
                s.insert(nxt);
            }
            else if (c == '1')
            {
                int nxt = (top - d + n) % n;
                s.insert(nxt);
            }
            else if (c == '?')
            {
                int nxt = (top + d) % n;
                s.insert(nxt);
                nxt = (top - d + n) % n;
                s.insert(nxt);
            }
        }
        q=s;
        s.clear();
    }
    if (q.count(0) == 1)
    {
        q.erase(0);
        q.insert(n);
    }
    cout << q.size() << endl;
    for (auto ss : q)
        cout << ss << " ";
    cout << endl;
}
void solve()
{
    n = read();
    m = read();
    x = read();
    for (int i = 1; i <= m; i++)
    {
        rem[i].second = read();
        rem[i].first = getchar();
    }
    bfs();
    return;
}
int main()
{
    //clock_t start, end;
    //freopen("data.in", "r", stdin);
    //start = clock();
    // IOS;
    int t = read();
    while (t--)
    {
        solve();
    }
    //end = clock();                                                            // 结束时间
    //cout << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl; // 输出时间（单位：ｓ）
    system("pause");
    return 0;
}

单一行建桥怎么分析？方程是什么？

单行建桥的方程是否涉及了太多的无效遍历？如何优化？

连续个桥的最小总价值如何维护？

对单一行而言，线性方程属于是已经怼到了脸上：

设表示在使用个桥墩后到达位置且在 位置放置桥墩的最小代价，则有：

边界条件为（切记不能是，否则可能出现第一个桥不放墩子），显然可以进行线性优化： 这里注意到，每一次转移中间都涉及了大量的暴力比较，所以采用小根堆结构优化。堆中维护数对（)记录所到的位置以及最小代价，以代价为关键字生成小根堆，每次取对顶元素比较和目标位置的距离，不大于即可选择相加并将计算结果入堆，如此维护即可达到级别查询最小值。

对于连续的​组桥，维护最小价值线性扫，每次移动不要全部叠加，维护前缀和即可。

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int maxn = 200005;
int dp[maxn];
int a[maxn];
int n, m, k, d;
typedef struct node
{
    int pos;
    int value;
    bool operator<(const node &x) const
    {
        return x.value < value;
    }
} node;
void solve()
{
    vector<int> ans(1);
    cin >> n >> m >> k >> d;
    for (int ip = 1; ip <= n; ip++)
    {
        memset(dp, 0x3f3f3f, sizeof(dp));
        dp[1] = 1;
        for (int i = 1; i <= m; i++)
        {
            cin >> a[i];
            a[i]++;
        }
        priority_queue<node> q;
        q.push({1, 1});
        for (int i = 2; i <= m; i++)
        {
            while (!q.empty())
            {
                if (i - q.top().pos > d + 1)
                    q.pop();
                else
                    break;
            }
            dp[i] = q.top().value + a[i];
            q.push({i, dp[i]});
        }
        ans.push_back(dp[m]);
    }
    int final, cnt = 0;
    for (int i = 1; i <= k; i++)
        cnt += ans[i];
    final = cnt;
    for (int i = k + 1; i <= n; i++)
    {
        final = min(final, min(cnt, cnt + ans[i] - ans[i - k]));
        cnt += ans[i] - ans[i - k];
    }
    cout << final << endl;
    return;
}
signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

最大段在哪儿？长度为多少？需不需要维护第二大值？

如果没有点能够落在最大段内，还有没有别的可能位置落点？如果有点能落在最大值里面的时候，还需不需要这种特殊处理？

回忆_ 、_、函数对于从开始的数组的返回值特点与处理。

设最大段位置，超过个点的时候维护第二大段长度.

对于目标，去重（重复的计算结果一样，凭空增加复杂度）后从小到大排序，对于每一个,二分爆搜落在区间内的。

存在，则暴力枚举分割出来的长度和比较取最大。

否则若不存在的时候，爆搜第一个满足的点，加入，和最大段比较长度。

爆搜时,

,（第一个大于的）

.（第一个小于的）

如果（即没搜到），令上界。

必要条件，否则区间内没有符合要求的点。

#pragma GCC Optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int minn = numeric_limits<int>::min();
const int maxx = numeric_limits<int>::max();
const int N = 2e5 + 9;
int n, m, k;
int a[N], d[N], f[N];
int f_1 = -1, f_2 = -2;
pair<int, int> f1;
void init()
{
    f_1 = -1;
    f_2 = -2;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i >= 2)
        {
            int tar = a[i] - a[i - 1];
            if (tar >= f_1)
            {
                f_2 = f_1;
                f_1 = tar, f1 = {i - 1, i};
            }
            else if (tar >= f_2)
            {
                f_2 = tar;
            }
        }
    }
    for (int i = 1; i <= m; i++)
        cin >> d[i];
    for (int i = 1; i <= k; i++)
        cin >> f[i];
    sort(d + 1, d + 1 + m);
    sort(f + 1, f + 1 + k);
    m=unique(d+1,d+1+m)-d-1;
    k=unique(f+1,f+1+k)-f-1;
}
void print()
{
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= m; i++)
    {
        cout << d[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= k; i++)
    {
        cout << f[i] << " ";
    }
    cout << endl;
}
void solve()
{
    cin >> n >> m >> k;
    init();
    //print();
    int ans = f_1;
    for (int i = 1; i <= m; i++)
    {
        if (d[i] + f[k] < a[f1.first])
            continue;
        int ll = upper_bound(f + 1, f + 1 + k, a[f1.first] - d[i]) - f;
        int rr = lower_bound(f + 1, f + 1 + k, a[f1.second] - d[i]) - f - 1;
        int tt=lower_bound(f+1,f+1+k,a[n]-d[i])-f;
        if(tt>k)tt=k;
        int calc = minn;
        if (ll <= rr)
            for (int j = ll; j <= rr; j++)
            {
                calc = max(d[i] + f[j] - a[f1.first], a[f1.second] - (d[i] + f[j]));
                if (n >= 3)
                {
                    calc = max(calc, f_2);
                }
                ans = min(ans, calc);
            }
        else
        {
            calc=f_1;
            if (d[i] + f[k] - a[tt] > 0)
                calc = max(calc, d[i] + f[tt] - a[n]);
            ans = min(ans, calc);
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    system("pause");
    return 0;
}

去掉颜色属性，这是什么题？

有颜色属性的时候，如果到达了一条彩色线路上的任意一个点等价于直接到达了其他所有点，怎么才能维护这个性质？是缩点吗？

这个过程是否可以理解为，从一个颜色跳转到另一个颜色需要的代价，而接下来访问从属于这个颜色的所有点都是的代价？

这个性质能不能通过加点代表元素集合来实现？

设有个点，第个点表示颜色号为的集合点。

设<>之间的边为颜色则证明可选择跨点到达点。

添加边<>，边权为；<>，边权为.

同理添加反向边，则问题彻底转化成了单源最短路径。

使用队列优化_​秒解。

需注意的是，清除数组记录的时候应当正好的清除而不是直接暴力全部，否则超时。这需要维护记录的种类的大小，明显可以担当此任务。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f;
const int maxn = 4e5+1;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
typedef struct edge
{
    int v, w;
} edge;
vector<edge> connects[maxn];
typedef struct node
{
    int dis;
    int pos;
    bool operator<(const node &x) const
    {
        return x.dis < dis;
    }
} node;
int n, m;
int dist[maxn], vis[maxn];
set<int>colorrem;
void init()
{
    for (int i = 1; i <= n; i++)
    {
        vis[i] = false;
        connects[i].clear();
        dist[i] = INF;
    }
    for(auto it:colorrem)
    {
        vis[n+it]=false;
        connects[n+it].clear();
        dist[n+it]=INF;
    }
    colorrem.clear();
    return;
}
void add_edge(int u, int v, int color)
{
    connects[u].push_back({n + color, 1});
    connects[v].push_back({n + color, 1});
    connects[n + color].push_back({v, 0});
    connects[n + color].push_back({u, 0});
    colorrem.insert(color);
    return;
}
void Dijkstra_queue(int start, int end)
{
    dist[start] = 0;
    if (start == end)
    {
        cout << 0 << endl;
        return;
    }
    priority_queue<node> q;
    q.push((node){0, start});
    while (!q.empty())
    {
        int top = q.top().pos;
        q.pop();
        if (vis[top])
            continue;
        vis[top] = 1;
        for (auto p : connects[top])
        {
            int v = p.v;
            if (dist[v] > dist[top] + p.w)
            {
                dist[v] = dist[top] + p.w;
                q.push((node){dist[v], v});
            }
        }
    }
    cout << dist[end] << endl;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, color;
        cin >> u >> v >> color;
        add_edge(u, v, color);
    }
    int start, end;
    cin >> start >> end;
    Dijkstra_queue(start, end);
    init();
    return;
}
signed main()
{
    IOS;
    n=maxn;
    init();
    int t;
    cin >> t;
    while (t--)
        solve();
    system("pause");
    return 0;
}

数论题目，整数型离散，积性函数+筛法？

记函数表示有多少个题目要求的序列，那么

记函数表示有多少个题目要求的序列，那么

若,是否有？

注意到数据范围，不能暴力线性筛，但是查询有限，怎么处理？

首先想，当为质数的时候，

记当前个空格为有个，显然剩下的个位置都只能放,则最终结果为 根据二项式定理易得.

同理，对于为质数的次幂时，记当前个空格有个，那么剩下的个位置都有种选择()，则最终结果为 显然这里注意到，如果是积性函数也必然不是完全积性函数。

那么这个函数到底是不是积性函数呢？

分析时已经发现位数对于质数的计算仅影响最终的幂次方，所以我们可以直接取简化分析。

枚举两组样例和，不难发现两者都只有三组结果。

好巧不巧，有种结果，还恰巧对应上述样例组两两条目对应位置相乘。

考试的时候就可以直接蒙一发积性函数了，严格的积性证明如下: 注意到数据规模不适用于线性筛，所以采用慢速的分解质因数，然后积性相乘。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
int quickpow(int a, int b)
{
    int e = 1;
    while (b)
    {
        if (b & 1)
            (e *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return e;
}
bool isprime[100001];
bool vis[100001];
int primer[100001];
void euler()
{
    for (int i = 2; i <= 100000; i++)
    {
        if (!vis[i])
        {
            vis[i] = 1;
            isprime[i] = 1;
            primer[++primer[0]] = i;
        }
        for (int j = 1; j <= primer[0] && i * primer[j] <= 100000; j++)
        {
            vis[i * primer[j]] = 1;
            if (i % primer[j])
                break;
        }
    }
    return;
}
void solve()
{
    int n, m;
    cin >> n >> m;

    map<int, int> mp;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
            {
                mp[i]++;
                n /= i;
            }
        }
    }
    if (n > 1)
        mp[n]++;
    int ans = 1LL;
    for (auto p : mp)
    {
        (ans *= (quickpow(1 + p.second, m) - quickpow(p.second, m) + mod) % mod) %= mod;
    }
    cout << ans << endl;
    return;
}
signed main()
{
    IOS;
    // euler();
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

阶乘的递推好想，但是要按照阶乘的方式求阶乘逆元递推会爆出很大的复杂度()，因为调用了过多的快速幂。

根据逆元的倒数思想，​

来实现逆向线性倒推

void init()
{
    a[0] = 1;
    inva[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        a[i] = (a[i - 1] * i) % mod;
    }
    inva[maxn] = quickpow(a[maxn], mod - 2);
    for (int i = maxn - 1; i >= 1; i--)
    {
        inva[i] = (inva[i + 1] * (i + 1)) % mod;
    }
    return;
}

从排列开始想还是从线段开始想？

以什么为分类讨论标准？

显然，一个排列内有多种符合条件的线段，而一种线段可以多次出现在不同的排列里，故根据线段来想。

定义某两个数 所生成的线段的基础距离长度 为该两个数作为一组最大最小值 放在线段两端时 线段的*最大长度。称这两个数为基础线段参数，所生成的线段集和为基础线段集。

由题意，此时基础线段内部可进行全排列（即最大最小值不一定非得在两端，在基础线段内任何位置均可）

记有个数字，限定为，那么基础长度为时可能的基础线段参数共有个：

以参数为例子，在线段中间的个间隔点可以放置的数字有

共有个

故以参数​所能生成的满足条件的基础线段共有 将基础线段打包成一个数，和剩下的个数全排列得到的拥有这个基础线段的可能的排列总数 基础长度为的基础线段参数共有个，共得到 个积分。

故对分类求和，得到总结果为 Most Important 因为当且仅当 时才能让基础线段长度为 ，这部分计算上面是没有考虑的，需要额外加算。

#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int maxn = 1e7 + 1;
int rem = 0;
const int mod = 998244353;
int a[maxn + 1];
int inva[maxn + 1];
int quickpow(int a, int b)
{
    int e = 1;
    while (b)
    {
        if (b & 1)
            (e *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return e;
}
void init()
{
    a[0] = 1;
    inva[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        a[i] = (a[i - 1] * i) % mod;
    }
    inva[maxn] = quickpow(a[maxn], mod - 2);
    for (int i = maxn - 1; i >= 1; i--)
    {
        inva[i] = (inva[i + 1] * (i + 1)) % mod;
    }
    return;
}
int A(int n, int m)
{
    if (n == m)
        return a[n];
    return (a[n] * inva[n - m]) % mod;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = 0LL;
    if (k == 0)
    {
        ans += (n * a[n]) % mod;
    }
    for (int i = 1; i <= n - k - 1; i++)
    {
        ans = (ans + ((((n - k - i) * (i + 1) % mod) * i) % mod * A(k + i - 1, i - 1) % mod) * a[n - i] % mod) % mod;
    }
    cout << ans << endl;
    return;
}
signed main()
{
    init();
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

猜时间复杂度，问题，涉及到了按位操作(级别)，大概明确复杂度，线段树或者树状数组。

位操作，举一个特殊的，如查询，发现了什么？

对于不特殊的（所有位不全是），如何向特殊化转移？如果的位数大于，怎么做？小于呢？

比如说，查询

还有样例的

如果你已经想到不特殊化的化做特殊化的再枚举的情况，很遗憾，这么做思路是对的，但是会。最后一步的枚举还可以怎么优化？

这个题属实是一个脑瘫的题，位运算出在了角标上面。

观察到复杂度后开始向线段树和树状数组方向靠拢，但是这两个都是处理的连续的角标。

根据提示2的内容，枚举特殊的的时候，我们发现最终的结果就是 如果特殊的二进制长度比短，那么最后的结果就是 其中，

如果并不特殊，那么降一位查询后，补充查询到的部分角标异或和。

正如提示4所言，直接暴力查询剩下的部分会超时。

怎么处理？这时候可以直接把的最高位和的对应位分别进行位取反，进一步的递归操作。

这一步可以通过样例的​进行模拟实现。

关于连续区间求和和修改问题，直接扔给树状数组。注意树状数组的角标必须从开始，需要进行角标换算。

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define lowbit(x) x & (-x)
int flapBit(int a, int b) { return a ^ (1 << b); }
int quickpow(int a, int b)
{
    int e = 1;
    while (b)
    {
        if (b & 1)
            e *= a;
        a *= a;
        b >>= 1;
    }
    return e;
}
int bitsize(int x)
{
    if (x == 0)
        return 1;
    int cnt = 0;
    while (x)
    {
        cnt++;
        x >>= 1;
    }
    return cnt;
}
// 低位清0，长度为清零的部分
int lbitsetzero(int x, int length)
{
    for (int i = 1; i <= length; i++)
    {
        x >>= 1;
    }
    for (int i = 1; i <= length; i++)
        x <<= 1;
    return x;
}
// 生成全是1的二进制数，长度为length
int creat(int length)
{
    if (length == 0)
        return 0;
    return quickpow(2, length) - 1;
}
const int maxn = 6e5 + 1;
int tree[maxn], a[maxn];
void add(int pos, int i)
{
    for (int p = pos; p <= maxn; p += lowbit(p))
    {
        tree[p] += i;
    }
    return;
}
void reset(int pos, int i)
{
    add(pos + 1, i - a[pos + 1]);
    a[pos + 1] = i;
    return;
}
int query(int pos)
{
    pos++;
    int sum = 0;
    for (int p = pos; p; p -= lowbit(p))
    {
        sum += tree[p];
    }
    return sum;
}
int calc(int i, int x)
{
    if (x == 0)
        return a[i + 1];
    int ilen = bitsize(i);
    int xlen = bitsize(x);
    if (x == quickpow(2, xlen) - 1)
    {
        int tar = i;
        tar = lbitsetzero(tar, xlen);
        return query(tar + x) - query(tar - 1);
    }
    else
    {
        int now = creat(xlen - 1);
        int ans = calc(i, now);
        ans += calc(flapBit(i, xlen - 1), flapBit(x, xlen - 1));
        return ans;
    }
}
void modify(int i, int x)
{
    reset(i, x);
    return;
}
signed main()
{
    IOS;
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(i, a[i]);
    }
    while (q--)
    {
        int x, y;
        int op;
        cin >> op >> x >> y;
        if (op == 1)
            modify(x, y);
        else
            cout << calc(x, y) << endl;
    }
    system("pause");
    return 0;
}