# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
528651 | colazcy | Slon (COCI15_slon) | C++17 | 3 ms | 1732 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e5 + 100;
ll exgcd(const ll a,const ll b,ll &x,ll &y){
if(!b){
x = 1,y = 0;
return a;
}
let res = exgcd(b,a % b,y,x);
y -= (a / b) * x;
return res;
}
char str[maxn];
int p,mod,n;
struct poly{
int k,b;
poly operator + (const poly &rhs)const{
return poly{(k + rhs.k) % mod,(b + rhs.b) % mod};
}
poly operator - (const poly &rhs)const{
return poly{(k - rhs.k + mod) % mod,(b - rhs.b + mod) % mod};
}
poly operator * (const poly &rhs)const{
return poly{int((1ll * k * rhs.b + 1ll * b * rhs.k) % mod),int(1ll * b * rhs.b % mod)};
}
void print()const{
debug("%dx + %d\n",k,b);
}
};
struct Token{
int id;
poly v;
// 0 : poly
// 1 : *
// 2 : +
// 3 : -
// 4 : )
// 5 : (
};
int pri(const int id){
if(id == 0)return 0;
if(id == 1)return 1;
if(id == 2 || id == 3)return 2;
if(id == 4)return 4;
if(id == 5)return 5;
assert(false);
}
poly resolve(){
std::vector<Token> expr;
[&expr](){
std::vector<Token> seq;
[&seq](){
for(int l = 1,r;l <= n;l = r + 1){
r = l;
if(std::isdigit(str[l]) || str[l] == 'x'){
if(str[l] == 'x')seq.push_back(Token{0,poly{1,0}});
else{
int s = str[l] - '0';
while(std::isdigit(str[r + 1]))s = (s * 10 + str[++r] - '0') % mod;
seq.push_back(Token{0,poly{0,s}});
}
}else if(str[l] == '*')seq.push_back(Token{1});
else if(str[l] == '+')seq.push_back(Token{2});
else if(str[l] == '-')seq.push_back(Token{3});
else if(str[l] == ')')seq.push_back(Token{4});
else if(str[l] == '(')seq.push_back(Token{5});
else assert(false);
}
}();
std::stack<Token> stk;
for(let x : seq)
if(x.id == 5)stk.push(x);
else{
if(x.id == 4){
while(stk.top().id != 5){
expr.push_back(stk.top());
stk.pop();
}
stk.pop();
}else{
while(!stk.empty() && pri(stk.top().id) < pri(x.id)){
expr.push_back(stk.top());
stk.pop();
}
stk.push(x);
}
}
while(!stk.empty())expr.push_back(stk.top()),stk.pop();
}();
// for(let t : expr)debug("%d (%d,%d)\n",t.id,t.v.k,t.v.b);
std::stack<poly> stk;
for(let x : expr)
if(x.id == 0)stk.push(x.v);
else if(x.id == 1){
assert(!stk.empty());
let b = stk.top(); stk.pop();
assert(!stk.empty());
let a = stk.top(); stk.pop();
stk.push(a * b);
}else if(x.id == 2){
assert(!stk.empty());
let b = stk.top(); stk.pop();
assert(!stk.empty());
let a = stk.top(); stk.pop();
stk.push(a + b);
}else if(x.id == 3){
assert(!stk.empty());
let b = stk.top(); stk.pop();
assert(!stk.empty());
let a = stk.top(); stk.pop();
stk.push(a - b);
}else assert(false);
assert(!stk.empty());
return stk.top();
}
int main(){
// std::freopen("slon.in.1","r",stdin);
// std::freopen("slon.out","w",stdout);
std::scanf("%s",str + 1);
std::scanf("%d %d",&p,&mod);
n = std::strlen(str + 1);
let f = resolve();
f.print();
let k = f.k,b = f.b;
ll x,t;
let g = exgcd(k,mod,x,t);
assert((p - b) % g == 0);
x *= (p - b) / g;
let m = std::abs(mod / g);
x %= m;
x += m;
x %= m;
std::printf("%lld\n",x);
std::fclose(stdin);
std::fclose(stdout);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |