首页 > 其他分享 >2023冲刺国赛模拟 13.1

2023冲刺国赛模拟 13.1

时间：2023-06-06 19:00:25浏览次数：45  
标签：include return int 置换 国赛 13.1 2023 now mod

T1 铲雪

通过打表可以发现 \(2^{23}\equiv 2^{47}\pmod{998244352}\) ，因此对于前 \(22\) 次平方操作，直接暴力修改即可，超出 \(22\) 的平方操作，对每个位置维护长度为 \(24\) 的平方数组，那么每次操作就是简单的数组循环移动，线段树维护即可。

code 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <iostream>
using namespace std;
const int max1 = 1e5;
const int mod = 998244353;

int n, m, A[max1 + 5][24];

void Add ( int &x, int y )
{
    x += y;
    if ( x >= mod )
        x -= mod;
    return;
}

int Quick_Power ( int base, int p )
{
    int res = 1;
    while ( p )
    {
        if ( p & 1 )
            res = 1LL * res * base % mod;
        p >>= 1;
        base = 1LL * base * base % mod;
    }
    return res;
}

map <int, int> pos;

struct Bit
{
    int tree[max1 + 5];

    #define lowbit(now) ( now & -now )

    void Clear ()
    {
        memset(tree + 1, 0, sizeof(int) * n);
        return;
    }

    void Insert ( int now, int x )
    {
        while ( now <= n )
        {
            Add(tree[now], x);
            now += lowbit(now);
        }
        return;
    }

    int Query ( int now )
    {
        int res = 0;
        while ( now )
        {
            Add(res, tree[now]);
            now -= lowbit(now);
        }
        return res;
    }

    int Query ( int L, int R )
    {
        return ( Query(R) - Query(L - 1) + mod ) % mod;
    }
}Tree1;

struct Segment_Tree
{
    #define lson(now) ( now << 1 )
    #define rson(now) ( now << 1 | 1 )

    struct Data
    {
        int val[24], head, tag;
    }tree[max1 * 4 + 5];

    void Push_Up ( int now )
    {
        tree[now].head = 0;
        int L = tree[lson(now)].head, R = tree[rson(now)].head;
        for ( int i = 0; i < 24; i ++ )
        {
            tree[now].val[i] = 0;
            Add(tree[now].val[i], tree[lson(now)].val[L]);
            Add(tree[now].val[i], tree[rson(now)].val[R]);
            L = L == 23 ? 0 : L + 1;
            R = R == 23 ? 0 : R + 1;
        }
        return;
    }

    void Push_Down ( int now )
    {
        if ( tree[now].tag )
        {
            tree[lson(now)].head = ( tree[lson(now)].head + tree[now].tag ) % 24;
            tree[rson(now)].head = ( tree[rson(now)].head + tree[now].tag ) % 24;
            tree[lson(now)].tag += tree[now].tag;
            tree[rson(now)].tag += tree[now].tag;
            tree[now].tag = 0;
        }
        return;
    }

    void Build ( int now, int L, int R )
    {
        memset(tree[now].val, 0, sizeof(tree[now].val)); tree[now].head = tree[now].tag = 0;
        if ( L == R )
            return;
        
        int mid = L + R >> 1;
        Build(lson(now), L, mid);
        Build(rson(now), mid + 1, R);
        return;
    }

    void Insert ( int now, int L, int R, int p, int x )
    {
        if ( L == R )
        {
            tree[now].head = tree[now].tag = 0; tree[now].val[0] = x;
            for ( int i = 1; i < 24; i ++ )
                tree[now].val[i] = 1LL * tree[now].val[i - 1] * tree[now].val[i - 1] % mod;
            return;
        }

        Push_Down(now);
        int mid = L + R >> 1;
        if ( p <= mid )
            Insert(lson(now), L, mid, p, x);
        else
            Insert(rson(now), mid + 1, R, p, x);
        Push_Up(now);
        return;
    }

    void Update ( int now, int L, int R, int ql, int qr )
    {
        if ( L >= ql && R <= qr )
        {
            tree[now].head = tree[now].head == 23 ? 0 : tree[now].head + 1;
            ++tree[now].tag;
            return;
        }

        Push_Down(now);
        int mid = L + R >> 1;
        if ( ql <= mid )
            Update(lson(now), L, mid, ql, qr);
        if ( qr > mid )
            Update(rson(now), mid + 1, R, ql, qr);
        Push_Up(now);
        return;
    }

    int Query ( int now, int L, int R, int ql, int qr )
    {
        if ( L >= ql && R <= qr )
            return tree[now].val[tree[now].head];
        
        Push_Down(now);
        int mid = L + R >> 1, res = 0;
        if ( ql <= mid )
            Add(res, Query(lson(now), L, mid, ql, qr));
        if ( qr > mid )
            Add(res, Query(rson(now), mid + 1, R, ql, qr));
        return res;
    }
}Tree2;

int main ()
{
    freopen("snow.in", "r", stdin);
    freopen("snow.out", "w", stdout);

    scanf("%d%d", &n, &m); Tree1.Clear(); Tree2.Build(1, 1, n);
    for ( int i = 1; i <= n; i ++ )
    {
        scanf("%d", &A[i][0]);
        A[i][0] = Quick_Power(A[i][0], mod - 2);
        for ( int k = 1; k < 24; k ++ )
            A[i][k] = 1LL * A[i][k - 1] * A[i][k - 1] % mod;
        pos[i] = 0; Tree1.Insert(i, A[i][0]);
    }

    pos[n + 1] = 0;

    int opt, L, R, ans;
    while ( m -- )
    {
        scanf("%d%d%d", &opt, &L, &R);
        if ( !opt )
        {
            Tree2.Update(1, 1, n, L, R);

            while ( true )
            {
                int p = pos.lower_bound(L) -> first;
                if ( p > R )
                    break;

                L = p + 1;
                Tree1.Insert(p, mod - A[p][pos[p]]);
                if ( pos[p] == 22 )
                {
                    pos.erase(pos.find(p));
                    Tree2.Insert(1, 1, n, p, A[p][23]);
                }
                else
                {
                    ++pos[p];
                    Tree1.Insert(p, A[p][pos[p]]);
                }
            }
        }
        else
        {
            ans = ( Tree1.Query(L, R) + Tree2.Query(1, 1, n, L, R) ) % mod;
            printf("%d\n", ans);
        }
    }

    return 0;
}

T2 抽卡

设 \(f(S)\) 表示当前先手行动，剩余卡牌组成集合 \(S\) 时的期望权值和，设 \(g(S)\) 表示当前后手行动，剩余卡牌组成集合 \(S\) 时的期望权值和。

考虑转移，以 \(f(S)\) 转移为例，枚举随机选取的集合 \(T\) （由于 \(T\) 越大，可选卡牌越多，因此先手会使 \(T\) 集合尽可能大），设合法的 \(T\) 集合有 \(cnt\) 个，存在转移：

\[f(S)=\tfrac{1}{cnt}\sum_{T\subseteq S, |T|\le m}\max(\max_{i\in T}(a_i+g(S-\{i\})), g(S)) \]

同理：

\[g(S)=\tfrac{1}{cnt}\sum_{T\subseteq S, |T|\le m}\min(\min_{i\in T}(a_i+f(S-\{i\})), f(S)) \]

容易发现转移存在后效性，比较显然的思路使枚举 \(f(S)\) 的值，带入计算，找到计算结果与枚举结果相等的值。

优化只需要发现随之枚举值的增大，求解值同样增大，但是求解值增大速度较小，简单画函数图像可以发现求解值与枚举值之差存在单调性，因此可以二分求解。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int max1 = 15, max2 = 1 << 15;
const double eps = 1e-8;

int n, m, k, A[max1 + 5], sum;
vector <int> sit[max2 + 5];
double f[max2 + 5], g[max2 + 5], tmp1[max2 + 5], tmp2[max2 + 5];

void Solve ( int S, double val )
{
    int siz = sit[S].size();
    g[S] = 0;
    for ( auto T : sit[S] )
        g[S] += min(tmp1[T], val) / siz;

    f[S] = 0;
    for ( auto T : sit[S] )
        f[S] += max(tmp2[T], g[S]) / siz;

    return;
}

int main ()
{
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &k);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &A[i]), sum += A[i];

    for ( int S = 0; S < 1 << n; S ++ )
    {
        if ( __builtin_popcount(S) >= k )
        {
            if ( __builtin_popcount(S) <= m )
                sit[S].push_back(S);
            else
            {
                for ( int T = S; T; T = ( T - 1 ) & S )
                    if ( __builtin_popcount(T) == m )
                        sit[S].push_back(T);
            }
        }
    }

    for ( int S = 0; S < 1 << n; S ++ )
    {
        int pop = __builtin_popcount(S);
        if ( pop == k )
            f[S] = g[S] = 0;
        else if ( pop > k )
        {
            for ( auto T : sit[S] )
            {
                tmp1[T] = sum;
                for ( int i = 1; i <= n; i ++ )
                    if ( T >> i - 1 & 1 )
                        tmp1[T] = min(tmp1[T], A[i] + f[S ^ 1 << i - 1]);
            }

            for ( auto T : sit[S] )
            {
                tmp2[T] = -sum;
                for ( int i = 1; i <= n; i ++ )
                    if ( T >> i - 1 & 1 )
                        tmp2[T] = max(tmp2[T], A[i] + g[S ^ 1 << i - 1]);
            }

            double L = 0, R = sum;
            while ( R - L > eps )
            {
                double mid = 0.5 * ( L + R ); Solve(S, mid);
                if ( f[S] < mid )
                    R = mid;
                else
                    L = mid;
            }
        }
    }

    printf("%.8lf\n", f[( 1 << n ) - 1]);

    return 0;
}

T3 樟

考虑一条边 \((i, j)\) ，根据题目要求，一定存在边 \((p_i, p_j)\) ，继续推导，一定存在边 \((p_{p_i}, p_{p_j})\) ，继续推导，一定存在边 \((p_{p_{p_i}}, p_{p_{p_j}})\) ，容易发现这构成置换环的关系。

于是考虑两个置换环的连边，以大小为 \(2,4\) 的置换环为例：

容易发现图中不存在环，因此这样的连边可能形成树。

猜想到置换环之间的连边不存在环可能与 \(\gcd\) 有关，因此考虑大小为 \(4,6\) 的置换环：

（其中 \(1, 2, 3, 4, 5, 6\) 为一个置换环， \(7, 8, 9, 10\) 位一个置换环）

容易发现连边中存在环，一定无法构成一棵树。

于是猜想一个结论：只有大小存在倍数关系的置换环间存在连边，并且连边方案数为较小的环的大小。

此时观察到，大小大于 \(2\) 的置换环中的点两两之间不能存在连边，因此如果需要将整棵树连通，需要大小为 \(1\) 或大小为 \(2\) 的置换环。

如果存在大小为 \(1\) 的置换环，显然这些置换环形成树，容易通过 prufer 序列求解这棵树的方案数。

考虑将其余大小的环挂到这棵树上，设当前枚举的大小为 \(i\) ，置换环个数为 \(c_i\) ，由于大小相同的置换环之间可能存在连边，因此需要枚举当前大小的所有置换环构成的连通块个数 \(k\) ，考虑对这个存在 \(k\) 个连通块的森林进行计数，建立虚点 \(0\) ，将森林中所有树的根节点与 \(0\) 连边，容易发现此时形成的新树中，存在 \(k-1\) 个位置在 prufer 序列上数值为 \(0\) ，其余位置任意，因此方案数为 \(\binom{c_i-1}{k-1}c_i^{c_i-k}\) 。

因此大小为 \(i\) 的置换环对答案的贡献为

\[\sum_{k=1}^{c_i}\binom{c_i-1}{k-1}c_i^{c_i-k}\times i^{c_i-k}\times (\sum_{d|i, d<i}(c_d\times d))^k \]

如果不存在大小为 \(1\) 的置换环，考虑使用大小为 \(2\) 的置换环进行代替，这些环构成树的方案数为 \((2c_2)^{c_2-1}\) ，之后仍然枚举剩余大小的环连接到树上即可。

code 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int max1 = 5e5;
const int mod = 998244353;

int T, n, A[max1 + 5], bin[max1 + 5], sum[max1 + 5];
bool vis[max1 + 5];
int fac[max1 + 5], ifac[max1 + 5], inv[max1 + 5];

int C ( int n, int m )
{
    if ( n < m || n < 0 || m < 0 )
        return 0;
    return 1LL * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int Quick_Power ( int base, int p )
{
    int res = 1;
    while ( p )
    {
        if ( p & 1 )
            res = 1LL * res * base % mod;
        p >>= 1;
        base = 1LL * base * base % mod;
    }
    return res;
}

void Work ()
{
    scanf("%d", &n);

    memset(bin + 1, 0, sizeof(int) * n);
    memset(sum + 1, 0, sizeof(int) * n);
    memset(vis + 1, 0, sizeof(bool) * n);

    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &A[i]);

    for ( int i = 1; i <= n; i ++ )
    {
        if ( !vis[i] )
        {
            int x = i, len = 0;
            while ( !vis[x] )
            {
                ++len;
                vis[x] = true;
                x = A[x];
            }
            ++bin[len];
        }
    }

    for ( int i = 1; i <= n; i ++ )
    {
        if ( !bin[i] )
            continue;

        for ( int k = 2; k * i <= n; k ++ )
            sum[i * k] = ( sum[i * k] + 1LL * bin[i] * i ) % mod;
    }

    int ans = 0;
    if ( bin[1] )
    {
        if ( bin[1] == 1 )
            ans = 1;
        else
            ans = Quick_Power(bin[1], bin[1] - 2);

        for ( int i = 2; i <= n; i ++ )
        {
            if ( !bin[i] )
                continue;

            int trans = 0;
            for ( int k = 1; k <= bin[i]; k ++ )
                trans = ( trans + 1LL * C(bin[i] - 1, k - 1) * Quick_Power(bin[i], bin[i] - k) % mod * Quick_Power(i, bin[i] - k) % mod * Quick_Power(sum[i], k) % mod ) % mod;

            ans = 1LL * ans * trans % mod;
        }
    }
    else if ( bin[2] )
    {
        if ( bin[2] == 1 )
            ans = 1;
        else
            ans = 1LL * Quick_Power(bin[2], bin[2] - 1) * Quick_Power(2, bin[2] - 1) % mod;

        for ( int i = 3; i <= n; i ++ )
        {
            if ( !bin[i] )
                continue;

            int trans = 0;
            for ( int k = 1; k <= bin[i]; k ++ )
                trans = ( trans + 1LL * C(bin[i] - 1, k - 1) * Quick_Power(bin[i], bin[i] - k) % mod * Quick_Power(i, bin[i] - k) % mod * Quick_Power(sum[i], k) % mod ) % mod;

            ans = 1LL * ans * trans % mod;
        }
    }

    printf("%d\n", ans);
    return;
}

int main ()
{
    freopen("camphor.in", "r", stdin);
    freopen("camphor.out", "w", stdout);

    inv[1] = 1;
    for ( int i = 2; i <= max1; i ++ )
        inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for ( int i = 1; i <= max1; i ++ )
    {
        fac[i] = 1LL * fac[i - 1] * i % mod;
        ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
    }

    scanf("%d", &T);
    while ( T -- )
        Work();
    return 0;
}

标签：include,return,int,置换,国赛,13.1,2023,now,mod
From： https://www.cnblogs.com/KafuuChinocpp/p/17461458.html

相关文章

  • 欧奈儿行业 RPS 排名，一图览全貌 2023-06-06
    自动复盘2023-06-06k线图是最好的老师，点击详情图可以看到行业20日RPS的排名，最底下子图是行业rps走势线跟踪板块总结：成交额超过100亿排名靠前，macd柱由绿转红公众hao:醉卧梦星河欧奈尔行业RPS排名天天更新追踪主力行业趋势更容......
  • 自考总结：202304考期
    考虑成绩昨天刚出，打算做下2023年4月考期的总结。报考202304考期报了三科：数据结构导论、管理经济学、信息系统开发与管理。这三科之中，除了信息系统开发与管理已经考过2次了，数据结构导论上次学了弃考了（考前复习不及时，没去考），管理经济学是首次报考。备考由于之前信息系统开发与......
  • 透过软考高项上半年真题，看2023下半年考试趋势｜上午计算题篇
    2023年上半年软考已经过去了半个多月，想必你对分的兴奋感已经淡去了不少，所以是时候拿出一版有建设性的分析文章出来了（发布早了可能你的兴趣点也不在这上面，哈哈）“建设性”通常是针对未来而言的，对信息系统项目管理师而言，未来并不远，也就5个月之后的事情2023年上半年的考试，特别是高项，是......
  • SCM Manager XSS漏洞复现（CVE-2023-33829）
    一、漏洞描述漏洞简述SCM-Manager是一款开源的版本库管理软件，同时支持subversion、mercurial、git的版本库管理。安装简单，功能较强，提供用户、用户组的权限管理，有丰富的插件支持。由于在MIT的许可下是开源的，因此它允许被用于商业用途，而且其代码可以在GitHub上获取到。该项目......
  • Pycharm 2023.1.2 破解版安装教程（附激活码,亲测有效）
    第一步：下载Pycharm安装包访问Pycharm官网，下载Pycharm2023.1.2版本的安装包，下载链接如下:https://www.jetbrains.com/pycharm/download打开页面后，点击 Download 按钮,等待Pycharm专业版下载完毕。第二步：安装Pycharm2023.1.2版本如果电脑之前有安装老版本Pycharm，需......
  • 2023-06-06 hexo 去除博客中的“嗯..! 目前共计”字样
    注意：我使用的是next主题。找到路径：你的博客\themes\hexo-theme-next\layout，修改archive.swig文件：修改前：<spanclass="archive-page-counter">{%setcheers%}{%setposts_length=site.posts.length%}{%ifposts_length>210%}{%s......
  • 2023年5月31日吴曦远202283820011实验五
    task1_1.pycode:withopen('data1.txt','r',encoding='utf-8')asf:data=f.readlines()n=0print(data)forlineindata:ifnotline.strip()=='':n+=1print(n)output:note:ifdelet"not"......
  • Photoshop 2023 v24.6 Beta 直装爱国版本ps
    win用户看这PsBeta最新直装版本已更新教程免破解。https://www.88appp.com/10714.htmlMac用户看这PsBeta最新直装版本已更新教程免破解。https://www.88appp.com/10742.html注意问题常见问题星球会更新https://t.zsxq.com/0eCxJEDoI......
  • 共话出海、布局全球，融云WICC2023 · 泛娱乐出海嘉年华广州收官！
    （移步公众号点击图片三折购买《社交泛娱乐出海作战地图》）6月2日，“WICC·泛娱乐出海嘉年华”在广州成功举办，圆满收官。关注【融云全球互联网通信云】了解更多本届嘉年华由高端峰会、圆桌会议、露营派对三部分组成，融云CEO董晗、白鲸出海创始人兼CEO魏方丹；融云CTO岑裕、Goog......
  • 2023年国内十大低代码平台盘点，他们的优点是什么？
    首先我们要知道，什么是低代码平台？低代码平台是一种通过图形化或可视化的方式来快速构建业务应用和软件系统的开发工具。它的核心思想在于用低门槛、高效率和更快的速度来解决软件开发过程中复杂性和繁琐性的问题，从而提高企业的数字化转型和业务创新能力。相对于传统的编程开发模式......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99