为什么我开了int128才过

P7077 [CSP-S2020] 函数调用

zhizhizhiwang @ 2024-11-26 20:04:34

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

template <typename T>
void read(T &x)
{
    int f = 1;
    x = 0;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-')f = -f;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x = f * x;
}

template <typename T, typename... Args>
void read(T &x, Args& ... args)
{
    read(x);
    read(args...);
}

template <typename T>
void print(T const t)
{
    T x = t;
    if(x < 0) x = -x;
    if(x > 9)print(x / 10);
    putchar(x % 10 + '0');
}

void print(char const *x)
{
    for(size_t i = 0, end = strlen(x);i < end; i++)
    {
        putchar(x[i]);
    }
}

template<typename T, typename... Args>
void print(T x, Args... args)
{
    print(x);
    print(args...);
}
#define int __int128

int const N = 1e6 + 10, MOD = 998244353;

int n, m, q;
vector<int> graph1[N], graph2[N];
int in1[N], in2[N], data[N];

struct Func
{
    int type;
    int add, pos;
    int mul;
    int cnt;
} func[N];

Func *x = &func[0];

void topo1()
{
    queue<int> q;
    for(int i = 0;i <= m;i ++)
    {
        in1[i] = graph2[i].size();
        if(in1[i] == 0) q.push(i);
    }
    while(not q.empty())
    {
        int u = q.front();
        q.pop();
        for(int n : graph1[u])
        {
            func[n].mul = func[n].mul % MOD * func[u].mul % MOD;
            in1[n] --;
            if(in1[n] == 0) q.push(n);
        }
    }
}

void topo2()
{
    queue<int> q;
    for(int i = 0;i <= m;i++)
    {
        in2[i] = graph1[i].size();
        if(in2[i] == 0) q.push(i);
    }
    while(not q.empty())
    {
        int u = q.front();
        q.pop();
        int64_t mul = 1;
        for(int i = graph2[u].size(); i > 0; i --)
        {
            int n = graph2[u][i - 1];
            x = &func[n];
            x -> cnt = x -> cnt + mul % MOD * func[u].cnt  % MOD;
            mul = mul * x -> mul % MOD;
            in2[n]--;
            if(in2[n] == 0) q.push(n);
        }
    }
}

int32_t main()
{
    read(n);
    for(int i = 1;i <= n;i ++) read(::data[i]);
    read(m);
    func[0].mul = 1;
    for(int i = 1;i <= m; i++)
    {
        x = &func[i];
        read(x -> type);
        if(x -> type == 1)
        {
            read(x -> pos, x -> add);
            x -> mul = 1;
        }
        else if(x -> type == 2)
        {
            read(x -> mul);
        }
        else if(x -> type == 3)
        {
            int end;
            x -> mul = 1;
            read(end);
            for(int v, j = 1;j <= end; j++)
            {
                read(v);
                graph1[v].push_back(i);
                graph2[i].push_back(v);
            }
        }
    }

    read(q);
    func[0].cnt = 1;
    for(int v, i = 0;i < q;i ++)
    {
        read(v);
        graph1[v].push_back(0);
        graph2[0].push_back(v);
    }
    topo1();
    topo2();

    for(int i = 1;i <= n;i ++)
    {
        ::data[i] = ::data[i] % MOD * func[0].mul % MOD;
    }

    for(int i = 1;i <= m; i++)
    {
        x = &func[i];
        if(x -> type == 1) ::data[x -> pos] = (::data[x -> pos] + x -> cnt % MOD * x -> add) % MOD;
    }

    for(int i = 1;i <= n; i++) print(::data[i] % MOD, " ");

}   

__int128 100pts

int64_t 75pts
非常不理解,我觉得我取模也都取了


|