//{ <defines>
#include <bits/stdc++.h>
using namespace std;
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")
#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)
#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _ << ' ' <<
#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back
#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;
inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());
template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
int md = 998244353;
inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}
int m_bpow(ll A, ll b) {
int a = A % md;
ll ans = 1;
for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
(ans *= ans) %= md;
if(p & b)
(ans *= a) %= md;
}
re ans;
}
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e5 + 5;
struct f {
int a, b;
f operator* (const f t) const {
re {
(ll(a) * t.b + ll(b) * t.a) % md,
ll(b) * t.b % md
};
}
f operator+ (const f t) const {
re {
(a + t.a) % md,
(b + t.b) % md
};
}
void invert() {
a = !a ? 0 : md - a;
b = !b ? 0 : md - b;
}
};
f eval(char *s, int &n) {
if(*s == 'x') {n = 1; re {1, 0};}
int z = 0;
for(n = 0; s[n] >= '0' && s[n] <= '9'; ++n)
((z *= 10) += s[n] - '0') %= md;
return {0, z};
}
f rec(char *s, int n, int *c) {
bool neg = false;
bool mul = false;
list<f> t;
for(int i = 0; i < n; ) {
int m;
f z;
if(s[i] == '(') {
m = c[i] + 1;
z = rec(s + i + 1, c[i] - 1, c + i + 1);
} else {
z = eval(s + i, m);
}
if(mul) {
t.back() = t.back() * z;
mul = false;
} else {
if(neg) {
z.invert();
neg = false;
}
t.push_back(z);
}
char op = s[i + m];
if(op == '-') neg = true;
if(op == '*') mul = true;
i += m + 1;
}
f res{0, 0};
for(const auto &i : t) res = res + i;
re res;
}
void solve() {
string s; cin >> s;
int n = s.size();
s += '#';
int p;
cin >> p >> md;
stack<int> st;
int c[n];
for(int i = 0; i < n; ++i) {
if(s[i] == '(') {
st.push(i);
}
if(s[i] == ')') {
c[st.top()] = i - st.top();
st.pop();
}
}
assert(st.empty());
f a = rec(&s[0], n, c);
for(int x = 0; x < md; ++x) {
if((1ll * x * a.a + a.b) % md != p) continue;
cout << x << endl;
return;
}
cout << "wat\n";
exit(5);
}
int main() {
#ifdef _LOCAL
freopen("in.txt", "r", stdin);
int tests; cin >> tests;
for(int test = 1; test <= tests; ++test) {
cerr << "case #" << test << endl;
solve();
cerr << endl;
}
#else
// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
#endif
return 0;
}
Compilation message
slon.cpp: In function 'int m_bpow(ll, ll)':
slon.cpp:51:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
~~~^~~~~~~~~~~~~~~~~~~~
slon.cpp: In member function 'f f::operator*(f) const':
slon.cpp:70:41: warning: narrowing conversion of '(((((ll)((int)((const f*)this)->f::a)) * ((ll)((int)t.f::b))) + (((ll)((int)((const f*)this)->f::b)) * ((ll)((int)t.f::a)))) % ((ll)md))' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
(ll(a) * t.b + ll(b) * t.a) % md,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
slon.cpp:71:25: warning: narrowing conversion of '((((ll)((int)((const f*)this)->f::b)) * ((ll)((int)t.f::b))) % ((ll)md))' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
ll(b) * t.b % md
~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
640 KB |
Output is correct |
| 10 |
Correct |
2 ms |
768 KB |
Output is correct |
