洛谷三月月赛 P5240 Derivation

小 R 学会微积分中求导这一概念后,他的数学老师要求他开始做一部分导数的练习题加深自己的理解。

但颖悟绝伦的小 R 对繁复的练习题并不感兴趣。他希望你帮他设计一个程序,计算一个给定函数 $f(x)$ 的导数。

第一行一个正整数 T,表示小 R 要完成的练习题数量,亦即测试数据的组数。
每组测试数据的第一行是一个非空字符串,描述了输入的函数 $f(x)$。设 $p=998244353$。

字符串中可能包含的元素有:

1、系数为 $1$ 的单项式,包括 $x^2,x^0$ 等,我们保证指数为非负整数为 $1$ 时不省略,不会超过 $p-1$。所有幂号用 ^ 代替。
2、常数,如 $0,19260817$ 等;我们保证一切常数是非负整数且不超过 $p-1$。
3、复合函数。将以上两种函数组合的方式可以为加乘幂,括号等。数学中会省略乘号和括号,但我们保证任意情况下都不省略(也不会无意义冗余,即不存在 ((x)),(3)+(4));保证任何指数都是常数,即不存在 $x^{g(x)}$的情况。

测试数据的第二行为两个整数,值在$[0,p)$之间。你需要输出两个整数,表示这些整数代入导函数后的值模 $p$ 的结果。

本题中认为 $0^0=1$。

这道题也是很神= =

首先求导不求导的,先把树建出来,然后就会发现这个题的本质还是合并左右孩子。但是有一点很神,就是合并时要用扩展欧拉定理合并,原因是我们存在^这个运算。然后就考虑我们可以存储当x=v时对所有扩欧展开时的模数取模,更新的时候按秩更新就好了= =

还有就是在调这题时,我发现了一个以前程序的bug。

关于建树时的鬼畜判断,我当时是这么加的判断:

1
2
3
4
5
6
7
8
9
10
11
12
void Init(){
tp = 0, memset(brac, 0, sizeof(brac)) ;
for (rr int i = 1 ; i <= N ; ++ i){
if (In[i] == '(') stk[++ tp] = i ;
if (In[i] == ')') brac[i] = stk[tp], brac[stk[tp]] = i, tp -- ;
}
}
blablabla....
inline int build(int l, int r){
if (brac[l] == r) l ++, r -- ;
blablabla...
}

这东西每次memset显然会超时,于是便采用一个退化版本

1
2
3
4
inline int build(int l, int r){ 
if (In[l] == '(' && In[r] == ')') l ++, r -- ; // 1
blablabla...
}

tm当时自己因为这个调了好久也是很佛了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#define rr register
#define ll long long

int mod[MAXM], n, v ;
int phi(int x){
int ret = x ;
for (int i = 2 ; i * i <= x ; ++ i)
if (!(x % i)){
ret = ret / i * (i - 1) ;
while (!(x % i)) x /= i ;
}
if (x > 1) ret = ret / x * (x - 1) ; return ret ;
}
void _prework(){
for (int i = Mod ; i > 1 ; i = phi(i))
mod[++ n] = i ; mod[++ n] = 1, mod[++ n] = 1 ;
}

int brac[MAXN], stk[MAXN], tp ;
char op[MAXN], In[MAXN] ; int N, T ;
int root, L[MAXN], R[MAXN], tot ; ll val[MAXN] ;

inline bool isop(char x){
return x == '+' || x == '*' || x == '^' ;
}
void Init(){
for (rr int i = 1 ; i <= N ; ++ i){
if (In[i] == '(') stk[++ tp] = i ;
if (In[i] == ')') brac[i] = stk[tp], brac[stk[tp]] = i, tp -- ;
}
}
inline int build(int l, int r){
if (In[l] == '(' && In[r] == ')') l ++, r -- ; // 1
rr int rt = 0, rt1 = 0, rt2 = 0, x = 0 ;
for (int i = l ; i <= r ; ++ i){
if (In[i] == '(') i = brac[i] + 1 ; if (i > r) break ;
if (In[i] == '+' && !isop(In[i - 1])) { rt = i ; break ; }
if (In[i] == '*') rt1 = i ; if (In[i] == '^' && !rt2) rt2 = i ;
}
if (rt) x = rt ; else if (rt1) x = rt1 ; else x = rt2 ;
if (!x){
x = r ;
if (In[r] == 'x') op[x] = 'X', val[x] = 1 ;
else op[x] = '?', sscanf(In + l, "%lld", &val[x]), val[x] %= Mod ;
L[x] = R[x] = 0 ; return x ;
}
op[x] = In[x], L[x] = build(l, x - 1), R[x] = build(x + 1, r) ; return x ;
}
struct Node{
ll y[MAXM], dy[MAXM] ;
};
ll mul(ll a,ll b,ll p){ // 2
return a * b < p ? a * b : a * b % p + p ;
}
ll add(ll a,ll b,ll p){ // 2
return a + b < p ? a + b : (a + b) % p + p ;
}
ll expow(ll a, ll b, ll p){
ll res = 1 ;
while (b){
if (b & 1) res = mul(res, a, p) ;
a = mul(a, a, p) ; b >>= 1 ;
}
return res ;
}
Node dp(int x){
Node res ;
if (!L[x] && !R[x]){
if (op[x] == 'X')
for (int i = 1 ; i <= n ; ++ i)
res.y[i] = v % mod[i], res.dy[i] = 1 ;
else for (int i = 1 ; i <= n ; ++ i)
res.y[i] = val[x] % mod[i], res.dy[i] = 0 ;
}
else {
Node l = dp(L[x]), r = dp(R[x]) ;
if (op[x] == '+')
for (int i = 1 ; i <= n ; ++ i)
res.y[i] = add(l.y[i], r.y[i], mod[i]),
res.dy[i] = add(l.dy[i], r.dy[i], mod[i]) ;
else if (op[x] == '*')
for (int i = 1 ; i <= n ; ++ i)
res.y[i] = mul(l.y[i], r.y[i], mod[i]),
res.dy[i] = add(mul(l.dy[i], r.y[i], mod[i]), mul(l.y[i], r.dy[i], mod[i]), mod[i]) ;
else{
rr ll calc ;
res.y[n] = res.dy[n] = 0 ;
for (int i = n - 1 ; i >= 1 ; -- i) // 1
res.y[i] = expow(l.y[i], r.y[i + 1], mod[i]),
calc = (!(l.y[i] % mod[i]) && (r.y[i + 1] % mod[i + 1] == 1)) ?
1 : expow(l.y[i], (r.y[i + 1] + mod[i + 1] - 1) % mod[i + 1], mod[i]),
res.dy[i] = mul(mul(l.dy[i], r.y[i], mod[i]), calc, mod[i]) ;
//calc: 此题认为0^0=1,因此判一下。s
}
}
return res ;

}
int main(){
_prework() ;
cin >> T ; int i ;
while (T --){
In[1] = '(', scanf("%s", (In + 2)) ;
N = strlen(In + 1), In[++ N] = ')' ;
Init(), tot = 0, root = build(1, N);
for (i = 0 ; i < 2 ; ++ i){
cin >> v ; Node res = dp(root) ;
printf("%d%c", res.dy[1] % Mod, " \n"[i == 1]) ;
}
}
return 0 ;
}

还有,就是当时自己觉得自己已经理解了怎么操作就开始瞎写,结果就开始疯狂地挂,于是发现了这两个函数:

1
2
3
4
5
6
ll mul(ll a,ll b,ll p){ // 2
return a * b < p ? a * b : a * b % p + p ;
}
ll add(ll a,ll b,ll p){ // 2
return a + b < p ? a + b : (a + b) % p + p ;
}

平心而论,这两个函数是最不起眼的两个函数……但是对于某些老年OI降智选手确实致命性的打击:这两个函数不是凭空存在的,是为了配合扩展欧拉定理的

基本形式大概就是:

$$n^k\equiv \begin{matrix} \qquad\ n^{[k\ \ mod \ \ \varphi(m)]+\varphi(m)} \ \ (k\geq \varphi(m))\\ n^k \qquad\ (k<\varphi(m)) \end{matrix} \qquad\ (mod \ \ m)$$

也就是说最后的$+p$是必要的= = 这也是很佛。。


然后就是我当时还奇怪为什么兔队写的这么快,结果写上一篇文章时发现原来是自己的复杂度写假了,如果按上文中的写,复杂度应该是$O(q|S|\log|S|\log^2p)$。

于是为了优化掉这个log我们需要写一遍后缀表达式版的求导= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <cstring>
#include <iostream>

#define MAXM 100
#define MAXN 100010
#define ll long long
#define Mod 998244353

#define rr register
using namespace std ;

struct Node{ ll y[MAXM], dy[MAXM] ; };
char stk[MAXM] ; Node Ans[MAXN] ; int ans, i, j, tp, pt ;
char In[MAXN], op[MAXN], res[MAXN] ; int T, N, L, mod[MAXM], n ; ll val[MAXN] ;

int phi(int x){
int ret = x ;
for (int i = 2 ; i * i <= x ; ++ i)
if (!(x % i)){
ret = ret / i * (i - 1) ;
while (!(x % i)) x /= i ;
}
if (x > 1) ret = ret / x * (x - 1) ; return ret ;
}
void _prework(){
for (int i = Mod ; i > 1 ; i = phi(i))
mod[++ n] = i ; mod[++ n] = 1, mod[++ n] = 1 ;
}
inline ll mul(ll a,ll b,ll p){ return a * b < p ? a * b : a * b % p + p ; }
inline ll add(ll a,ll b,ll p){ return a + b < p ? a + b : (a + b) % p + p ; }
inline ll expow(ll a, ll b, ll p){
rr ll res = 1 ;
while (b){
if (b & 1) res = mul(res, a, p) ;
a = mul(a, a, p) ; b >>= 1 ;
}
return res ;
}

inline int calc(const char &x){
if (x =='(') return 1 ;
if (x =='+') return 2 ;
if (x =='*') return 3 ;
if (x =='^') return 4 ; return 0 ;
}
inline bool Comp(const char &a, const char &b){ return calc(a) >= calc(b) ; }

int main(){
_prework() ; cin >> T ;
while (T --){
scanf("%s", In + 1), N = strlen(In + 1) ;
for (i = 1 ; i <= N ; ++ i){
ll ret = 0 ;
if (isdigit(In[i])){
while (isdigit(In[i]))
ret = (ret << 1) + (ret << 3) + In[i] - '0', ++ i ;
i --, val[++ L] = ret, res[L] = 'N' ;
}
else if (In[i] == 'x') val[++ L] = 1, res[L] = 'X' ;
else if (In[i] == '(') stk[++ tp] = In[i] ;
else if (In[i] == ')'){
while (stk[tp] != '(')
res[++ L] = stk[tp --] ;
tp -- ;
}
else {
while (tp && Comp(stk[tp], In[i]))
res[++ L] = stk[tp --] ; stk[++ tp] = In[i] ;
}
}
while (tp) res[++ L] = stk[tp --] ;
for (int o = 1 ; o <= 2 ; ++ o){
rr int v ; scanf("%d", &v) ;
for (j = 1 ; j <= L ; ++ j){
rr Node ret ;
if (!calc(res[j])) {
if (res[j] == 'X')
for (i = 1 ; i <= n ; ++ i)
ret.y[i] = v % mod[i], ret.dy[i] = 1 ;
else for (i = 1 ; i <= n ; ++ i)
ret.y[i] = val[j] % mod[i], ret.dy[i] = 0 ;
Ans[++ pt] = ret ; continue ;
}
rr Node p1 = Ans[pt --] ; rr Node p2 = Ans[pt --] ;
if (res[j] == '+')
for (int i = 1 ; i <= n ; ++ i)
ret.y[i] = add(p1.y[i], p2.y[i], mod[i]),
ret.dy[i] = add(p1.dy[i], p2.dy[i], mod[i]) ;
else if (res[j] == '*')
for (int i = 1 ; i <= n ; ++ i)
ret.y[i] = mul(p1.y[i], p2.y[i], mod[i]),
ret.dy[i] = add(mul(p1.dy[i], p2.y[i], mod[i]), mul(p1.y[i], p2.dy[i], mod[i]), mod[i]) ;
else{
rr ll calcc ; swap(p1, p2) ;
ret.y[n] = ret.dy[n] = 0 ;
for (int i = n - 1 ; i >= 1 ; -- i) // 1
ret.y[i] = expow(p1.y[i], p2.y[i + 1], mod[i]),
calcc = (!(p1.y[i] % mod[i]) && (p2.y[i + 1] % mod[i + 1] == 1)) ?
1 : expow(p1.y[i], (p2.y[i + 1] + mod[i + 1] - 1) % mod[i + 1], mod[i]),
ret.dy[i] = mul(mul(p1.dy[i], p2.y[i], mod[i]), calcc, mod[i]) ;
}
Ans[++ pt] = ret ;
}
printf("%lld ", Ans[pt].dy[1] % Mod), pt -- ;
}
L = 0, puts("") ;
}
return 0 ;
}

写完我才发现我的大常数是救不了的了,兔爷写的60ms,我写的1120ms,这tm20倍的常数宛如写了$\rm{|S|\log|S|}$……不过说会话比建树的快了些。

看了看题解似乎应该是兔爷多写了一层欧拉展开,于是又消掉一个log = =

$O(q|S|\log^2 p)$

$O(q|S|\log |S| log^2 p)$

卡常真是荼毒人名= =