Submission #622428

#	Time	Username	Problem	Language	Result	Execution time	Memory
622428		inksamurai	Slon (COCI15_slon)	C++17	12 / 120	4 ms	724 KiB

slon

#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);
}

• Subtask 1: 12 / 120