#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3SgiE60 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class ...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
int binpow(int a,int b,int mod){
int res=1;
while(b){
if(b%2){
res=res*a%mod;
res%=mod;
}
a=a*a%mod;
a%=mod;
b/=2;
}
return res;
}
signed main(){
_3SgiE60;
string s;
cin>>s;
int need,mod;
cin>>need>>mod;
const int n=sz(s);
// k*x+l
auto digit=[&](char ch)->bool{
return ch>='0' and ch<='9';
};
auto operation=[&](char ch)->bool{
return ch=='+' or ch=='-' or ch=='*';
};
auto _get_id=[&](char ch)->int{
return ch=='+'?0:ch=='-'?1:2;
};
auto merge=[&](pii p,pii q,int t)->pii{
// print(t);
pii res;
if(t==2){
res.fi=p.fi*q.fi+p.fi*q.se%mod;
res.fi+=p.se*q.fi%mod;
res.se=p.se*q.se%mod;
}else if(t==1){
res.fi=(p.fi-q.fi+mod*mod)%mod;
res.se=(p.se-q.se+mod*mod)%mod;
}else if(t==0){
res.fi=(p.fi+q.fi)%mod;
res.se=(p.se+q.se)%mod;
}
res.fi%=mod;
res.se%=mod;
return res;
};
using T=pair<int,pii>;
int i=0;
auto dfs=[&](auto self)->pii{
if(i>=n) return {0,0};
vec(T) ops;
// type,val
while(i<n){
if(s[i]=='('){
i+=1;
pii np=self(self);
ops.pb(T(1,np));
}else if(s[i]==')'){
i+=1;
break;
}else{
if(operation(s[i])){
ops.pb(T(0,pii(_get_id(s[i]),0)));
i+=1;
}else{
pii np={0,0};
if(s[i]=='x'){
np={1,0};
i+=1;
}else{
int v=0;
while(digit(s[i])){
v=v*10+(s[i]-'0');
v%=mod;
i+=1;
}
np={0,v};
}
ops.pb(T(1,np));
}
}
}
vec(T) nops;
rep(i,sz(ops)){
if(ops[i].fi==0 and ops[i].se.fi==2){
assert(i and i<sz(ops)-1 and ops[i-1].fi==1);
pii p=ops[i-1].se;
for(int j=i;j<sz(ops);j+=2){
if(ops[j].se.fi!=2){
break;
}
p=merge(p,ops[j+1].se,2);
i=j+1;
}
nops.pb(T(1,p));
}else if(i==sz(ops)-1 or ops[i+1].se.fi!=2){
nops.pb(ops[i]);
}
}
// print("\n..... old operations ");
// for(auto tp:ops){
// print(tp.fi,tp.se.fi,tp.se.se);
// }
// print("\n.......");
ops=nops;
if(!sz(ops)) return {0,0};
assert(ops[0].fi==1);
pii p=ops[0].se;
for(int i=2;i<sz(ops);i+=2){
// print("ho",ops[i-1].se.fi);
assert(ops[i-1].fi==0);
p=merge(p,ops[i].se,ops[i-1].se.fi);
}
return p;
};
pii p=dfs(dfs);
// assert(p.fi==0 or gcd(p.fi,mod)==1);
p.se=(need-p.se+mod*mod)%mod;
int x=p.se*binpow(p.fi,mod-2,mod);
print(x%mod);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
