首页 > 其他分享 >2023省选武汉联测10

2023省选武汉联测10

时间：2023-04-20 21:13:35浏览次数：43  
标签：10 连通 省选 max1 int 联测 ans include mod

T1 矩阵

随机一个向量 \(V\) ，判断 \(V\times A\times B\) 是否等于 \(V\times C\) 即可，实质上我们在判断对于每个 \(i\in[1,n]\) \(\sum_{k=1}^nV_k\sum_{p=1}^{n}A_{k,p}B_{p,i}\) 是否等于 \(\sum_{k=1}^{n}V_kC_{k,i}\) 。

code

#include <cstdio>
#include <vector>
#include <utility>
#include <random>
#include <ctime>
using namespace std;
const int max1 = 3000;
const int mod = 998244353;
int T, n, A[max1 + 5][max1 + 5], B[max1 + 5][max1 + 5], C[max1 + 5][max1 + 5];
int L[max1 + 5], R[max1 + 5], tmp[max1 + 5];
vector < pair <int, int> > posA, posB;
void Work ()
{
    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= n; j ++ )
            scanf("%d", &A[i][j]);
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= n; j ++ )
            scanf("%d", &B[i][j]);
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= n; j ++ )
            scanf("%d", &C[i][j]);
    for ( int i = 1; i <= n; i ++ )
        L[i] = R[i] = rand() % mod;
    for ( int i = 1; i <= n; i ++ )
    {
        tmp[i] = 0;
        for ( int j = 1; j <= n; j ++ )
            tmp[i] = ( tmp[i] + 1LL * L[j] * A[j][i] ) % mod;
    }
    for ( int i = 1; i <= n; i ++ )
        L[i] = tmp[i];
    for ( int i = 1; i <= n; i ++ )
    {
        tmp[i] = 0;
        for ( int j = 1; j <= n; j ++ )
            tmp[i] = ( tmp[i] + 1LL * L[j] * B[j][i] ) % mod;
    }
    for ( int i = 1; i <= n; i ++ )
        L[i] = tmp[i];
    for ( int i = 1; i <= n; i ++ )
    {
        tmp[i] = 0;
        for ( int j = 1; j <= n; j ++ )
            tmp[i] = ( tmp[i] + 1LL * R[j] * C[j][i] ) % mod;
    }
    for ( int i = 1; i <= n; i ++ )
        R[i] = tmp[i];
    bool flag = true;
    for ( int i = 1; i <= n; i ++ )
        if ( L[i] != R[i] )
            flag = false;
    if ( flag )
        printf("Yes\n");
    else
        printf("No\n");
    return;
}
int main ()
{
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    srand(time(NULL));
    scanf("%d", &T);
    while ( T -- )
        Work();
    return 0;
}

T2 错排

容易发现前 \(m\) 个数一定错排，后 \(n-m\) 个数存在 \(m\) 个数没有限制，因此设总共 \(n\) 个数，前 \(m\) 个数没有限制，剩余数严格错排的方案数为 \(f_{n,m}\) ，那么答案为 \(\tfrac{(n-m)!}{(n-2m)!}f_{n-m,m}\) 。

当 \(m=0\) 时，有经典错排递推式， \(f_{n,0}=(n-1)(f_{n-1,0}+f_{n-2,0})\) ，考虑 \(m\ne 0\) 的情况，简单考虑 \(p_m\) 的情况，如果 \(p_m=m\) ，贡献为 \(f_{n-1,m-1}\) ，如果 \(p_m\ne m\) ，这相当于第 \(m\) 个数也存在限制，贡献为 \(f_{n,m-1}\) ，因此有递推式：

\[f_{n,m}=f_{n-1,m-1}+f_{n,m-1} \]

发现递推形似组合数，容易想到一种快速求解答案的思路：设阈值 \(B\) ，预处理所有满足 \(m=kB\) 的每个 \(f_{n,m}\) ，假设当前询问为 \(f_{n,m}\) ，显然答案为 \(\sum\binom{m\operatorname{mod}B}{n-t}f_{t,\lfloor\tfrac{m}{B}\rfloor}\) ，容易发现计算的复杂度为 \(O(B)\) 。

考虑如何进行预处理，题解给出的做法是生成函数，设 \(F_m(x)=\sum_{i=0}^{\infty}f_{i,m}x^i\) ，显然 \(F_m(x)=(x+1)F_{m-1}(x)\) ，那么 \(F_m(x)=(x+1)^mF_0(x)\) ，用多项式乘法预处理可以做到 \(O(n\sqrt{n\log n})\) ，但常数极大；另一种做法是直接递推，通过打表可以发现 \(f_{n,m}=(n-1)f_{n-1,m}+(n-1-m)f_{n-2,m}\) ，简单理解就是第 \(n\) 个数可以直接在 \(n-1\) 个数形成的错排的基础上交换，也可以交换 \((n-1-m)\) 个有限制的位置满足这些位置 \(p_i=i\) ，可以做到 \(O(n\sqrt{n})\) 。

code

#include <cstdio>
#include <algorithm>
using namespace std;
const int lim = 2e5, B = 447;
const int mod = 998244353;
int inv[lim + 5], fac[lim + 5], ifac[lim + 5], f[B + 5][lim + 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 Solve ( int n, int m )
{
    int k = m / B, t = m % B, ans = 0;
    for ( int i = max(0, n - t); i <= n; i ++ )
        ans = ( ans + 1LL * C(t, n - i) * f[k][i] ) % mod;
    return ans;
}
int main ()
{
    freopen("qwq.in", "r", stdin);
    freopen("qwq.out", "w", stdout);
    inv[1] = 1;
    for ( int i = 2; i <= lim; i ++ )
        inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
    fac[0] = 1, ifac[0] = inv[1];
    for ( int i = 1; i <= lim; i ++ )
        fac[i] = 1LL * fac[i - 1] * i % mod, ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
    for ( int i = 0; i <= B; i ++ )
    {
        int k = i * B;
        f[i][k] = fac[k], f[i][k + 1] = 1LL * fac[k] * k % mod;
        for ( int j = k + 2; j <= lim; j ++ )
            f[i][j] = ( 1LL * ( j - 1 ) * f[i][j - 1] + 1LL * ( j - 1 - k ) * f[i][j - 2] ) % mod;
    }
    int T, n, m, ans;
    scanf("%d", &T);
    while ( T -- )
    {
        scanf("%d%d", &n, &m);
        if ( n >= m + m )
            ans = 1LL * fac[n - m] * ifac[n - m - m] % mod * Solve(n - m, m) % mod;
        printf("%d\n", ans);
    }
    return 0;
}

T3 异或图

首先考虑快速求解 \(m=0\) 的答案，我们从高位向低位依次考虑，如果当前位存在位置 \(i\) 满足 \(a_i\) 这一位为 \(1\) ，并且 \(b_i\) 这一位为 \(0\) ，那么 \(b_i\) 的低位可以任意填写，此时只需要计算当前位异或值等于目标值并且其他数低位任意的方案数，根据这个性质，我们设 \(f_{i,0/1,0/1}\) 表示当前考虑了前 \(i\) 个数，此时这一位的异或值为 \(0/1\) ，是否存在一个位置 \(p\) ，满足 \(a_p\) 这一位为 \(1\) 并且 \(b_p\) 这一位为 \(0\) ，转移时考虑第 \(i\) 个数填 \(0/1\) 即可。（转移比较麻烦但是很简单，在此不再赘述）

考虑解决原问题，比较显然的思路是枚举边集进行容斥，钦定 \(s\) 集合内的边满足 \(b_u=b_v\) ，容斥系数为 \((-1)^{|s|}\) ，取连通块内最小的 \(a_i\) 作为限制 \(lim\) ，那么对于偶数大小的连通块，可以直接产生 \(lim\) 的贡献，对于奇数大小的连通块，它相当于一个 \(a_i=lim\) 的点，可以用 \(m=0\) 的算法求解，我们得到了一个 \(O(2^{|边集|}n\log w)\) 的暴力。

考虑枚举连通块而不是枚举边集，首先需要求解一个连通块的容斥系数，设 \(g_S\) 表示当 \(S\) 集合内所有点连通时，可行的边集的容斥系数之和，比较经典的套路是转化为边任选减去不连通的系数和，设 \(S\) 内部的点数为 \(siz\) ，边数为 \(cnt\) ，显然有初始化 \(g_S=[cnt=0\operatorname{and}siz=1]\) ，随意选定集合内一个点，枚举这个点所在的连通块进行容斥即可。

设 \(h_{s,t}\) 表示当前考虑了 \(s\) 集合内的点，奇数大小连通块内最小的点形成的集合为 \(t\) 的容斥系数和，转移时枚举下一个连通块即可（为了避免重复，枚举未选点组成集合的 \(lowbit\) 所在的连通块），发现 \(t\subseteq s\) ，因此可以用三进制壮压减少状态，复杂度为 \(O(4^n)\) ，但常数很小。

code

#include <cstdio>
using namespace std;
const int max1 = 15, max2 = 1 << 15, max3 = 14348907, max_bit = 60;
const int mod = 998244353;
int n, m, inv[max1 + 5];
bool edge[max1 + 5][max1 + 5];
long long a[max1 + 5], b[max1 + 5], C;
long long bit[max1 + 5][max_bit + 5];
int siz[max2 + 5], low[max2 + 5], Min[max2 + 5], f[max2 + 5], g[max2 + 5], power[max2 + 5];
int h[max3 + 5];
int Map[max2 + 5];
long long Bit ( int i, int j )
{
    if ( j == -1 )
        return 1LL;
    return bit[i][j] + 1LL;
}
int Solve ( int s )
{
    if ( ~Map[s] )
        return Map[s];
    int ans = 0;
    for ( int i = max_bit; i >= 0; i -- )
    {
        int f[2][2], tmp[2][2], now;
        f[0][0] = 1, f[0][1] = f[1][0] = f[1][1] = 0;
        now = 0;
        for ( int j = 1; j <= n; j ++ )
        {
            if ( !( s >> j - 1 & 1 ) )
                continue;
            tmp[0][0] = f[0][0], tmp[0][1] = f[0][1], tmp[1][0] = f[1][0], tmp[1][1] = f[1][1];
            if ( a[j] >> i & 1 )
            {
                f[0][0] = Bit(j, i - 1) % mod * tmp[1][0] % mod;
                f[0][1] = ( ( 1LL << i ) % mod * tmp[0][1] + Bit(j, i - 1) % mod * tmp[1][1] + tmp[0][0] ) % mod;
                f[1][0] = Bit(j, i - 1) % mod * tmp[0][0] % mod;
                f[1][1] = ( ( 1LL << i ) % mod * tmp[1][1] + Bit(j, i - 1) % mod * tmp[0][1] + tmp[1][0] ) % mod;
            }
            else
            {
                f[0][0] = Bit(j, i - 1) % mod * tmp[0][0] % mod;
                f[0][1] = Bit(j, i - 1) % mod * tmp[0][1] % mod;
                f[1][0] = Bit(j, i - 1) % mod * tmp[1][0] % mod;
                f[1][1] = Bit(j, i - 1) % mod * tmp[1][1] % mod;
            }
            now ^= a[j] >> i & 1;
        }
        if ( C >> i & 1 )
            ans = ( ans + f[1][1] ) % mod;
        else
            ans = ( ans + f[0][1] ) % mod;
        if ( now != ( C >> i & 1 ) )
            break;
    }
    long long sum = 0;
    for ( int i = 1; i <= n; i ++ )
    {
        if ( !( s >> i - 1 & 1 ) )
            continue;
        sum ^= a[i];
    }
    ans = ( ans + ( sum == C ) ) % mod;
    Map[s] = ans;
    return ans;
}
int main ()
{
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
    scanf("%d%d%lld", &n, &m, &C);
    for ( int i = 1; i <= n; i ++ )
        scanf("%lld", &a[i]);
    for ( int i = 1, u, v; i <= m; i ++ )
        scanf("%d%d", &u, &v), edge[u][v] = edge[v][u] = true;
    inv[0] = inv[1] = 1;
    for ( int i = 2; i <= n; i ++ )
        inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
    for ( int i = 1; i <= n; i ++ )
        inv[i] = 1LL * inv[i - 1] * inv[i] % mod;
    for ( int i = 0; i <= n; i ++ )
    {
        bit[i][0] = a[i] & 1;
        for ( int j = 1; j <= max_bit; j ++ )
            bit[i][j] = bit[i][j - 1] | ( a[i] & 1LL << j );
    }
    siz[0] = 0, low[0] = Min[0] = -1, f[0] = 0, g[0] = 1;
    for ( int s = 1; s < 1 << n; s ++ )
    {
        siz[s] = siz[s >> 1] + ( s & 1 );
        low[s] = Min[s] = ( s & 1 ) ? 1 : low[s >> 1] + 1;
        if ( s ^ ( 1 << low[s] - 1 ) && a[Min[s ^ ( 1 << low[s] - 1 )]] < a[low[s]] )
            Min[s] = Min[s ^ ( 1 << low[s] - 1 )];
        f[s] = f[s ^ ( 1 << low[s] - 1 )];
        for ( int i = 1; i <= n; i ++ )
            if ( ( s >> i - 1 & 1 ) && edge[i][low[s]] )
                ++f[s];
        if ( !f[s] )
            g[s] = siz[s] == 1;
        else
        {
            g[s] = 0;
            int tmp = s ^ ( 1 << low[s] - 1 );
            for ( int t = tmp & ( tmp - 1 ); ; t = ( t - 1 ) & tmp )
            {
                t ^= 1 << low[s] - 1;
                if ( !f[s ^ t] )
                    g[s] = ( g[s] - g[t] + mod ) % mod;
                t ^= 1 << low[s] - 1;
                if ( !t )
                    break;
            }
        }
    }
    int lim = 1, ans = 0;
    for ( int i = 1; i <= n; i ++ )
        lim = lim * 3;
    power[0] = 0;
    for ( int s = 1; s < 1 << n; s ++ )
        power[s] = power[s >> 1] * 3 + ( s & 1 );
    for ( int s = 0; s < 1 << n; s ++ )
        Map[s] = -1;
    h[0] = 1;
    for ( int s = 0; s < lim; s ++ )
    {
        if ( !h[s] )
            continue;
        int tmp = s, k = 0;
        for ( int i = 1; i <= n; i ++, tmp /= 3 )
            if ( !( tmp % 3 ) )
                k ^= 1 << i - 1;
        if ( k )
        {
            tmp = k ^ ( 1 << low[k] - 1 );
            for ( int t = tmp; ; t = ( t - 1 ) & tmp )
            {
                t ^= 1 << low[k] - 1;
                int new_s = s + power[t] + ( siz[t] & 1 ? power[1 << Min[t] - 1] : 0 ), up = ( ( siz[t] & 1 ) ? 1LL : a[Min[t]] + 1LL ) % mod * g[t] % mod;
                h[new_s] = ( h[new_s] + 1LL * h[s] * up ) % mod;
                t ^= 1 << low[k] - 1;
                if ( !t )
                    break;
            }
        }
        else
        {
            k = 0;
            tmp = s;
            for ( int i = 1; i <= n; i ++, tmp /= 3 )
                if ( tmp % 3 == 2 )
                    k ^= 1 << i - 1;
            ans = ( ans + 1LL * h[s] * Solve(k) ) % mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}

标签：10,连通,省选,max1,int,联测,ans,include,mod
From： https://www.cnblogs.com/KafuuChinocpp/p/17338343.html

相关文章

  • 2023省选武汉联测9
    T1背包问题模板比较套路的，我们考虑进行二进制拆分，对于数量\(A\)，我们首先从小到大拆分为\(1,2,4...2^k\)，对于剩余的\(w\)，我们直接按照它的二进制位拆分即可，这样问题转化为比较简单的\(0/1\)背包。由于\(b_i\)的范围很小，如果将物体体积用二进制数表示，发现二进制上为\(......
  • 2023省选武汉联测13
    T1构树直接\(O(n^2)\)暴力枚举连边即可。code#include<cstdio>#include<vector>#include<set>#include<utility>usingnamespacestd;constintmax1=1000;intn,Min[max1+5],Max[max1+5];vector<int>part[max1+5];intcolo......
  • # 2023省选武汉联测12
    T1图案首先是题解做法：考虑对于每个\(r\)，判断\(s[1,r]\)是否为一个图案，设\(r=ik+j\)，其中\(0\lej\lei\)，如果存在一组这样的\((i,j)\)满足\(s[1,r-i]=s[i+1,r]\)，那么\(s[1,r]\)是一个图案，考虑这样做的正确性，如果\(s[1,r-i]=s[i+1,r]\)，那么一定有\(s[i+1,r-2i]=s......
  • 2023省选武汉联测11
    T1游戏对于树上三点\((u,v,w)\)，一定存在一个点\(p\)满足\(p\tou\)与\(p\tov\)与\(p\tow\)的路径两两不重合，考虑枚举\(p\)计算答案，由于题目给定\(\operatorname{dis}(u,v),\operatorname{dis}(u,w),\operatorname{dis}(v,w)\)，因此我们首先用解方程的方法求解\(......
  • 洛谷 P1007 独木桥
    题目背景战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 11 个人通过。假如有 2......
  • 起泡法排序 用起泡法对10个数由小到大排序
    起泡排序是一种基础的排序算法，它通过比较相邻的两个数的大小来排序，如果前一个数比后一个数大，则交换这两个数的位置，这样一遍比较之后，最大的数就会被排在最后面，然后再重复进行这个过程，直到所有的数都被排好序为止。下面是使用起泡排序对10个数进行排序的步骤：初始化待排序数组：[5,......
  • selenium报错：This version of ChromeDriver only supports Chrome version 109 Curren
    前言：跟GPT交互，让其写一段代码，执行失败。经过排查验证，GPT写的代码没有问题，是本地环境问题。执行报错：selenium.common.exceptions.SessionNotCreatedException:Message:sessionnotcreated:ThisversionofChromeDriveronlysupportsChromeversion109Currentbrowser......
  • 1094 The Largest Generation
    Afamilyhierarchyisusuallypresentedbyapedigreetreewhereallthenodesonthesamelevelbelongtothesamegeneration.Yourtaskistofindthegenerationwiththelargestpopulation.InputSpecification:Eachinputfilecontainsonetestcase.E......
  • 1020 Tree Traversals
    Supposethatallthekeysinabinarytreearedistinctpositiveintegers.Giventhepostorderandinordertraversalsequences,youaresupposedtooutputthelevelordertraversalsequenceofthecorrespondingbinarytree.InputSpecification:Eachinput......
  • 第10周
    1、使用dockerfile制作nginx+php-fpm镜像，实现lnmp。2、使用dockerfile制作tomcat镜像，并实现对jsp测试页访问3、安装配置harbor服务，并将打包好的镜像提交到harbor仓库---------------------------------------------------------------------------------------------------------......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99