2023冲刺国赛模拟 7.0

标签：int sum max1 mid 国赛 7.0 2023 tfrac mod

T1 Matrix

很容易想到一个 \(O(n^4)\) 做法，用 uint128 压位，然后你发现它过了……

正解考虑分治，取出矩阵中间的列 \(mid\) ，由于跨越 \(mid\) 列的询问必然经过 \(mid\) 列上一点，因此对于 \(mid\) 左边的点，预处理每个点向右，向下可以到达的所有 \(mid\) 处的点，对于 \(mid\) 右边的点，预处理每个点向左，向上可以到达的所有 \(mid\) 处的点，使用 bitset 可以做到 \(O(\tfrac{n^3}{w})\) 预处理，之后对于每个跨过 \(mid\) 的询问，可以在 \(O(\tfrac{n}{q})\) 的复杂度下进行查询，总复杂度可以做到 \(O(\tfrac{n^2m\log m+nq}{w})\) 。

code

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

const int max1 = 500, max2 = 1e6;

int n, m, q;
char s[max1 + 5][max1 + 5];

struct Question
{
    int id, A, B, C, D;
    Question () {}
    Question ( int __id, int __A, int __B, int __C, int __D )
        { id = __id, A = __A, B = __B, C = __C, D = __D; }
};

vector <Question> qus[max1 + 5];

void Insert ( int L, int R, const Question &Q )
{
    int mid = L + R >> 1;
    if ( Q.C <= mid && Q.D >= mid )
        return qus[mid].push_back(Q);
    if ( Q.D < mid )
        Insert(L, mid - 1, Q);
    else
        Insert(mid + 1, R, Q);
    return;
}

bitset <max1 + 5> bit[max1 + 5][max1 + 5];
bitset <max2 + 5> ans;

void Solve ( int L, int R )
{
    if ( L > R )
        return;
    
    int mid = L + R >> 1;

    if ( !qus[mid].empty() )
    {
        for ( int i = 1; i <= n; i ++ )
        {
            bit[i][mid].reset();
            if ( s[i][mid] == '0' )
                bit[i][mid][i] = 1;
        }
        
        for ( int i = n; i >= 1; i -- )
        {
            for ( int j = mid - 1; j >= L; j -- )
            {
                if ( s[i][j] == '0' )
                {
                    bit[i][j] = bit[i][j + 1];
                    if ( i < n && s[i + 1][j] == '0' )
                        bit[i][j] |= bit[i + 1][j];
                }
                else
                    bit[i][j].reset();
            }
        }

        for ( int i = 1; i <= n; i ++ )
        {
            if ( i > 1 && s[i][mid] == '0' )
                bit[i][mid] |= bit[i - 1][mid];
            for ( int j = mid + 1; j <= R; j ++ )
            {
                if ( s[i][j] == '0' )
                {
                    bit[i][j] = bit[i][j - 1];
                    if ( i > 1 && s[i - 1][j] == '0' )
                        bit[i][j] |= bit[i - 1][j];
                }
                else
                    bit[i][j].reset();
            }
        }

        for ( auto Q : qus[mid] )
        {
            if ( Q.C == mid )
                ans[Q.id] = bit[Q.B][Q.D][Q.A];
            else
                ans[Q.id] = ( bit[Q.A][Q.C] & bit[Q.B][Q.D] ).any();
        }
    }
    Solve(L, mid - 1);
    Solve(mid + 1, R);
    return;
}

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

    scanf("%d%d%d", &n, &m, &q);
    for ( int i = 1; i <= n; i ++ )
        scanf("%s", s[i] + 1);
    for ( int i = 1, A, B, C, D; i <= q; i ++ )
    {
        scanf("%d%d%d%d", &A, &B, &C, &D);
        Insert(1, m, Question(i, A, B, C, D));
    }

    Solve(1, m);

    for ( int i = 1; i <= q; i ++ )
    {
        if ( ans[i] )
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}

T2 Travel

考虑枚举环的起点依次处理每个询问，断裂环上所有跨过起点的边（包括从起点出发和从起点结束的边），容易发现左右两边构成一些链，设左边链的条数为 \(x\) ，显然右边链的条数只能为 \(x,x+1,x-1\) ，假设当前我们知道左边和右边链的方案数为 \(A,B\) ，考虑进行合并，如果左右两边链的条数均为 \(x\) ，由于两侧的链存在顺序关系，显然有贡献 \((x!)^2\) ，由于从起点出发的边可以选择左右两个方向，因此有贡献 \(2\) ，如果左右两边链的条数为 \(x,x+1\) ，同样有贡献 \(x!(x+1)!\) ，此时从起点出发的边只能选择链的条数较多的方向，因此贡献为 \(1\) ，左右两边链的条数为 \(x,x-1\) 同理。

因此考虑 dp 左右两边链的方案数，设 \(f_{i,j}\) 表示从左向右考虑到第 \(i\) 个点，此时有 \(j\) 条链的方案数，转移只需要考虑新开一条链，将点连接在链头，将点连接到链尾，拼接两条链进行转移即可，需要注意的是，从左向右 dp 时需要保证链尾方向向右，同理从右向左 dp 时需要保证链尾方向向左。

code

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int max1 = 5000;
const int mod = 1e9 + 7;

int n; char s[max1 + 5];
int f[max1 + 5][max1 + 5], g[max1 + 5][max1 + 5], fac[max1 + 5];

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

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

    scanf("%s", s + 1); n = strlen(s + 1);
    
    f[0][0] = 1;
    for ( int i = 0; i <= n - 1; i ++ )
    {
        for ( int j = 0; j <= i; j ++ )
        {
            if ( !f[i][j] )
                continue;
            
            if ( s[i + 1] == '>' )
            {
                Add(f[i + 1][j], 1LL * f[i][j] * j % mod);
                Add(f[i + 1][j + 1], f[i][j]);
            }
            else
            {
                Add(f[i + 1][j], 1LL * f[i][j] * j % mod);
                if ( j > 1 )
                    Add(f[i + 1][j - 1], 1LL * f[i][j] * j % mod * ( j - 1 ) % mod);
            }
        }
    }
    
    g[n + 1][0] = 1;
    for ( int i = n + 1; i >= 2; i -- )
    {
        for ( int j = 0; j <= n + 1 - i; j ++ )
        {
            if ( !g[i][j] )
                continue;

            if ( s[i - 1] == '<' )
            {
                Add(g[i - 1][j], 1LL * g[i][j] * j % mod);
                Add(g[i - 1][j + 1], g[i][j]);
            }
            else
            {
                Add(g[i - 1][j], 1LL * g[i][j] * j % mod);
                if ( j > 1 )
                    Add(g[i - 1][j - 1], 1LL * g[i][j] * j % mod * ( j - 1 ) % mod);
            }
        }
    }

    fac[0] = 1;
    for ( int i = 1; i <= n; i ++ )
        fac[i] = 1LL * fac[i - 1] * i % mod;

    for ( int i = 1; i <= n; i ++ )
    {
        int ans = 0;
        
        for ( int k = 0; k <= min(i - 1, n - i); k ++ )
        {
            Add(ans, 1LL * f[i - 1][k] * g[i + 1][k] % mod * fac[k] % mod * fac[k] % mod * 2 % mod);
            Add(ans, 1LL * f[i - 1][k] * g[i + 1][k + 1] % mod * fac[k] % mod * fac[k + 1] % mod);
            Add(ans, 1LL * f[i - 1][k + 1] * g[i + 1][k] % mod * fac[k + 1] % mod * fac[k] % mod);
        }

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

    return 0;
}

T3 Number

我好菜……不会生成函数，也不会线性代数……

设 \(f_{i,j}\) 表示在第 \(i\) 次操作后原数为 \(j\) 的概率，存在转移：

\[f_{i,j}=\sum_{w=j}^{n}\tfrac{f_{i-1,w}}{w+1} \]

转移很有规律但是不好优化，考虑用生成函数刻画关系，设 \(F_i(x)=\sum_{k=0}^{n}f_{i,k}x^k\) ，那么

\[\begin{aligned} F_i(x)&=\sum_{k=0}^{n}f_{i,k}x^k\\ &=\sum_{k=0}^{n}\sum_{w=k}^{n}\tfrac{f_{i-1,w}}{w+1}x^k\\ &=\sum_{w=0}^{n}\tfrac{f_{i-1,w}}{w+1}\sum_{k=0}^{w}x^k\\ &=\sum_{w=0}^{n}\tfrac{f_{i-1,w}}{w+1}\times\tfrac{x^{w+1}-1}{x-1}\\ &=\tfrac{1}{x-1}\sum_{w=0}^{n}f_{i-1,w}\times\tfrac{x^{w+1}-1}{w+1}\\ &=\tfrac{1}{x-1}\sum_{w=0}^{n}f_{i-1,w}\int_1^x t^wdt\\ &=\tfrac{1}{x-1}\int_1^xF_{i-1}(t)dt \end{aligned} \]

这个 \(\int_1^xF_{i-1}(t)dt\) 看起来非常邪恶，考虑换成更常用的 \(\int_0^x\) （我从来没用过就是了），设 \(G_i(x)=F_i(x+1)\) ，同时设 \(G_i(x)=\sum_{k=0}^{n}g_{i,k}x^k\)，那么：

\[\begin{aligned} G_i(x)&=F_i(x+1)\\ &=\tfrac{1}{x}\int_1^{x+1}F_{i-1}(t)dt\\ &=\tfrac{1}{x}\int_0^{x}F_{i-1}(t+1)d(t+1)\\ &=\tfrac{1}{x}\int_0^{x}G_{i-1}(t)dt\\ &=\sum_{k=0}^{n}\tfrac{g_{i-1,k}}{k+1}x^k \end{aligned} \]

容易发现 \(g_{i,k}=\tfrac{g_{i-1,k}}{k+1}\) ，那么 \(g_{m,k}=\tfrac{g_{0,k}}{(k+1)^m}\) ，这十分友好，因此只需要考虑 \(f,g\) 数组之间的相互转化即可。

根据定义 \(G_i(x)=F_i(x+1)\) ，那么：

\[\begin{aligned} G_i(x)&=F_i(x+1)\\ &=\sum_{k=0}^{n}f_{i,k}(x+1)^{k}\\ &=\sum_{k=0}^{n}f_{i,k}\sum_{w=0}^{k}\binom{k}{w}x^w\\ &=\sum_{w=0}^{n}\sum_{k=w}^{n}f_{i,k}\binom{k}{w}x^w \end{aligned} \]

因此 \(g_{i,w}=\sum_{k=w}^{n}f_{i,k}\binom{k}{w}\) ，那么：

\[\begin{aligned} g_{i,w}&=\sum_{k=w}^{n}f_{i,k}\binom{k}{w}\\ &=\tfrac{1}{w!}\sum_{k=w}^{n}f_{i,k}k!\tfrac{1}{(k-w)!}\\ &=\tfrac{1}{w!}\sum_{k=0}^{n-w}f_{i,k+w}(k+w)!\tfrac{1}{k!} \end{aligned} \]

设 \(h_{i,k}=f_{i,n-k}(n-k)!\) ，那么：

\[g_{i,w}=\tfrac{1}{w!}\sum_{k=0}^{n-w}h_{i,n-k-w}\tfrac{1}{k!} \]

很容易使用 NTT 优化。

将 \(g\) 转化为 \(f\) 的过程可以使用二项式反演，推导过程和上述过程基本相同，在此不在赘述。

code

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

const int max1 = 1e5;
const int mod = 998244353, gmod = 3;

int n;
long long m;
int bit, total, rev[max1 * 4 + 5];
int f[max1 * 4 + 5], g[max1 * 4 + 5];

int inv[max1 * 4 + 5], fac[max1 * 4 + 5], ifac[max1 * 4 + 5];

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 Iterative_NTT ( int A[], int type, int len )
{
    for ( int i = 0; i < len; i ++ )
        if ( i < rev[i] )
            swap(A[i], A[rev[i]]);
        
    for ( int mid = 2; mid <= len; mid <<= 1 )
    {
        int wn = Quick_Power(gmod, ( mod - 1 ) / mid);
        if ( type == -1 )
            wn = Quick_Power(wn, mod - 2);

        for ( int i = 0; i < len; i += mid )
        {
            int w = 1;
            for ( int k = 0; k < mid >> 1; k ++ )
            {
                int x = A[i + k], y = 1LL * w * A[i + ( mid >> 1 ) + k] % mod;
                A[i + k] = ( x + y ) % mod;
                A[i + ( mid >> 1 ) + k] = ( x - y + mod ) % mod;
                w = 1LL * w * wn % mod;
            }
        }
    }

    if ( type == -1 )
    {
        int T = Quick_Power(len, mod - 2);
        for ( int i = 0; i < len; i ++ )
            f[i] = 1LL * f[i] * T % mod;
    }
    return;
}

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

    scanf("%d%lld", &n, &m);
    m %= mod - 1;
    for ( int i = 0; i <= n; i ++ )
        scanf("%d", &f[i]);
    
    bit = 1, total = 2;
    while ( total < n + n + 1 )
        total <<= 1, ++bit;
    
    rev[0] = 0;
    for ( int i = 1; i < total; i ++ )
        rev[i] = ( rev[i >> 1] >> 1 ) | ( i & 1 ) << bit - 1;

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

    for ( int i = 0; i <= n; i ++ )
        f[i] = 1LL * f[i] * fac[i] % mod;
    reverse(f, f + 1 + n);
    for ( int i = 0; i <= n; i ++ )
        g[i] = ifac[i];
    for ( int i = n + 1; i < total; i ++ )
        f[i] = g[i] = 0;
    
    Iterative_NTT(f, 1, total);
    Iterative_NTT(g, 1, total);
    for ( int i = 0; i < total; i ++ )
        f[i] = 1LL * f[i] * g[i] % mod;
    Iterative_NTT(f, -1, total);

    for ( int i = 0; i <= n; i ++ )
        f[i] = 1LL * f[i] * Quick_Power(Quick_Power(n - i + 1, m), mod - 2) % mod;
    
    for ( int i = 0; i <= n; i ++ )
    {
        if ( i & 1 )
            g[i] = mod - ifac[i];
        else
            g[i] = ifac[i];
    }

    for ( int i = n + 1; i < total; i ++ )
        f[i] = g[i] = 0;
    
    Iterative_NTT(f, 1, total);
    Iterative_NTT(g, 1, total);
    for ( int i = 0; i < total; i ++ )
        f[i] = 1LL * f[i] * g[i] % mod;
    Iterative_NTT(f, -1, total);
    
    reverse(f, f + 1 + n);
    for ( int i = 0; i <= n; i ++ )
        f[i] = 1LL * f[i] * ifac[i] % mod;
    
    for ( int i = 0; i <= n; i ++ )
        printf("%d ", f[i]);
    printf("\n");

    return 0;
}

标签：int,sum,max1,mid,国赛,7.0,2023,tfrac,mod
From： https://www.cnblogs.com/KafuuChinocpp/p/17426287.html

T1 Matrix

T2 Travel

T3 Number

相关文章

赞助商

阅读排行