$P5240 Derivation$

神仙题。
第一场月赛的题目我到第二场月赛完了才写【由此可见我是真的菜
题目就是个大模拟加乘显然，幂的话需要将原函数、导函数的函数值用扩展欧拉定理展开 $log$ 层。时间复杂度 $O(T |S| \log^2p)$
因为求导时要对指数减一，你可能会用加 (模数-1) 来实现，并且如果你的扩展欧拉定理写法是小于模数时是正常值，超过模数时用真实值 + 模数代替，就会导致错误，因为正常的快速幂中 $0^0=1$
但 $0^P=0$ $(P≠0)$
以下不是本人写的程序是验题人写的
#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 10005

#define eps 1e-12

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 + c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 998244353;

char s[MAXN],que[MAXN];

int val[2],tot,phi[MAXN];

vector<pii > sta[2];

bool f[2][MAXN][2];

int eu(int x) {

    int t = x;

    for(int i = 2 ; i <= x / i ; ++i) {

        if(x % i == 0) {

            t = t / i * (i - 1);

            while(x % i == 0) x /= i;

        }

    }

    if(x > 1) t = t / x * (x - 1);

    return t;

}

int fpow(int x,int c,int mod,bool &on) {

    int64 res = 1,t = x;

    if(c == 0) {on = 0;return 1;}

    if(x == 1 || x == 0) return x;

    while(c && !on) {

        res = res * x;--c;

        if(res >= MOD) {res %= mod;on = 1;break;}

    }

    while(c) {

        if(c & 1) res = res * t % mod;

        t = t * t % mod;

        c >>= 1;

    }

    return res;

}

void Solve() {

    scanf("%s",s + 2);

    read(val[0]);read(val[1]);

    s[1] = '(';

    int L = strlen(s + 1);

    s[L + 1] = ')';++L;

    sta[0].clear();sta[1].clear();

    tot = 0;

    int lev = 0;

    for(int i = 1 ; i <= L ; ++i) {

        if(s[i] >= '0' && s[i] <= '9') {

            if(s[i - 1] < '0' || s[i - 1] > '9') {

                for(int k = 0 ; k <= 1 ; ++k) {

                    int v = s[i] - '0';

                    sta[k].pb(mp(v,(lev == 0 ? 0 : v)));

                    f[k][sta[k].size() - 1][0] = 0;

                    f[k][sta[k].size() - 1][1] = 0;

                }

            }

            else {

                for(int k = 0 ; k <= 1 ; ++k) {

                    auto t = sta[k].back();

                    int64 a = 1LL * t.fi * 10 + s[i] - '0';

                    int64 b = 1LL * t.se * 10 + s[i] - '0';

                    if(a >= MOD) {

                        f[k][sta[k].size() - 1][0] = 1;

                        a %= phi[lev];

                    }

                    if(b >= MOD) {

                        f[k][sta[k].size() - 1][1] = 1;

                        b %= phi[max(lev - 1,0)];

                    }

                    if(lev == 0) b = 0;

                    t = mp(a,b);

                    sta[k].pop_back();sta[k].push_back(t);

                }

            }

        }

        else if(s[i] == ')') {

            if(!tot) break;

            if(que[tot] == '^') --lev;

            for(int k = 0 ; k <= 1 ; ++k) {

                int si = sta[k].size() - 1;

                auto t0 = sta[k][si - 1],t1 = sta[k][si];

                sta[k].pop_back();sta[k].pop_back();

                if(que[tot] == '^') {

                    if(f[k][si][0]) t1.fi += phi[lev + 1];

                    if(f[k][si][1]) t1.se += phi[lev];

                    if(lev) {

                        int a = fpow(t0.fi,t1.fi,phi[lev],f[k][si - 1][0]);

                        int b = fpow(t0.se,t1.se,phi[lev - 1],f[k][si - 1][1]);

                        sta[k].pb(mp(a,b));

                    }

                    else {

                        int a = fpow(t0.fi,t1.fi,MOD,f[k][si - 1][0]);

                        int b = 1LL * t1.se * t0.se % MOD;

                        if(t0.fi != 0)

                            b = 1LL * b * fpow(t0.fi,(1LL * t1.fi + (MOD - 2)) % (MOD - 1),MOD,f[k][si - 1][1]) % MOD;

                        else {

                            if(f[k][si][0]) b = 0;

                            else if(t1.fi - 1) b = 0;

                        }

                        sta[k].pb(mp(a,b));

                    }

                }

                else if(que[tot] == '+') {

                    f[k][si - 1][0] |= f[k][si][0];

                    f[k][si - 1][1] |= f[k][si][1];

                    t0.fi = t0.fi + t1.fi;

                    t0.se = t0.se + t1.se;

                    if(t0.fi >= MOD) {t0.fi %= phi[lev];f[k][si - 1][0] |= 1;}

                    if(t0.se >= MOD) {t0.se %= phi[max(0,lev - 1)];f[k][si - 1][1] |= 1;}

                    sta[k].pb(t0);

                }

                else if(que[tot] == '*') {

                    if(lev == 0) {

                        int64 a = 1LL * t0.fi * t1.fi % MOD;

                        int64 b = (1LL * t0.fi * t1.se % MOD + 1LL * t1.fi * t0.se % MOD) % MOD;

                        sta[k].pb(mp((int)a,(int)b));

                    }

                    else {

                        if((!f[k][si][0] && t1.fi == 0) || (!f[k][si - 1][0] && t0.fi == 0)) f[k][si - 1][0] = 0;

                        else f[k][si - 1][0] |= f[k][si][0];

                        if((!f[k][si][1] && t1.fi == 0) || (!f[k][si - 1][1] && t0.fi == 0)) f[k][si - 1][1] = 0;

                        else f[k][si - 1][1] |= f[k][si][1];

                        int64 a = 1LL * t0.fi * t1.fi;

                        int64 b = 1LL * t0.se * t1.se;

                        if(a >= MOD) {a %= phi[lev];f[k][si - 1][0] |= 1;}

                        if(b >= MOD) {b %= phi[lev - 1];f[k][si - 1][1] |= 1;}

                        sta[k].pb(mp((int)a,(int)b));

                    }

                }

            }

            --tot;

        }

        else if(s[i] == 'x') {

            sta[0].pb(mp(val[0],1));

            sta[1].pb(mp(val[1],1));

        }

        else {

            if(s[i] != '(') que[++tot] = s[i];

            if(s[i] == '^') ++lev;

        }

    }

    out(sta[0][0].se);space;out(sta[1][0].se);enter;

}

int main() {

#ifdef ivorysi

    freopen("f2.in","r",stdin);

#endif

    int T;

    read(T);

    phi[0] = MOD;

    for(int i = 1 ; i <= 10000 ; ++i) {

        phi[i] = eu(phi[i - 1]);

    }

    for(int i = 1 ; i <= T ; ++i) {

        Solve();

    }

}
巴特西

$P5240 Derivation$

最新文章

热门文章
