| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 622509 |
2022-08-04T10:48:27 Z |
inksamurai |
Slon (COCI15_slon) |
C++17 |
|
3 ms |
468 KB |
#include <bits/stdc++.h>
#include <utility>
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m < 2^31`
barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
} // namespace internal
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>
namespace atcoder {
long long pow_mod(long long x, long long n, int m) {
assert(0 <= n && 1 <= m);
if (m == 1) return 0;
internal::barrett bt((unsigned int)(m));
unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));
while (n) {
if (n & 1) r = bt.mul(r, y);
y = bt.mul(y, y);
n >>= 1;
}
return r;
}
long long inv_mod(long long x, long long m) {
assert(1 <= m);
auto z = internal::inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
// (rem, mod)
std::pair<long long, long long> crt(const std::vector<long long>& r,
const std::vector<long long>& m) {
assert(r.size() == m.size());
int n = int(r.size());
// Contracts: 0 <= r0 < m0
long long r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert(1 <= m[i]);
long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) {
std::swap(r0, r1);
std::swap(m0, m1);
}
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return {0, 0};
continue;
}
// assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)
// (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
// r2 % m0 = r0
// r2 % m1 = r1
// -> (r0 + x*m0) % m1 = r1
// -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
// -> x = (r1 - r0) / g * inv(u0) (mod u1)
// im = inv(u0) (mod u1) (0 <= im < u1)
long long g, im;
std::tie(g, im) = internal::inv_gcd(m0, m1);
long long u1 = (m1 / g);
// |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
if ((r1 - r0) % g) return {0, 0};
// u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
long long x = (r1 - r0) / g % u1 * im % u1;
// |r0| + |m0 * x|
// < m0 + m0 * (u1 - 1)
// = m0 + m0 * m1 / g - m0
// = lcm(m0, m1)
r0 += x * m0;
m0 *= u1; // -> lcm(m0, m1)
if (r0 < 0) r0 += m0;
}
return {r0, m0};
}
long long floor_sum(long long n, long long m, long long a, long long b) {
long long ans = 0;
if (a >= m) {
ans += (n - 1) * n * (a / m) / 2;
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
long long y_max = (a * n + b) / m, x_max = (y_max * m - b);
if (y_max == 0) return ans;
ans += (n - (x_max + a - 1) / a) * y_max;
ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
return ans;
}
} // namespace atcoder
#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};
int pi=i;
vec(T) ops;
// type,val
while(i<n){
if(s[i]=='('){
i+=1;
pii np=self(self);
// if(pi==0) print(i,np.fi,np.se);
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));
}
}
}
// if(pi==0){
// for(auto tp:ops){
// print(tp.fi,tp.se.fi,tp.se.se);
// }
// }
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].fi==0 and 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)==1) return ops[0].se;
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);
}
// if(i==0){
// print(p.fi,p.se);
// }
// pii p={0,0};
return p;
};
pii p=dfs(dfs);
// print(p.fi,p.se);
// print(mod);
vec(ll) m={mod,p.fi};
vec(ll) r={0,(p.se-need+mod)%mod};
pii res=atcoder::crt(r,m);
print(max((res.fi-(p.se-need+mod)%mod)/p.fi,res.fi/mod));
// print(res.fi,res.se);
// // 25815*x + 31528 = y
// for(int i=0;i<mod;i++){
// if((p.fi*i+p.se)%mod==need){
// cout<<i<<"\n";
// return 0;
// }
// }
}
Compilation message
slon.cpp: In instantiation of 'main()::<lambda(auto:23)> [with auto:23 = main()::<lambda(auto:23)>; pii = std::pair<long long int, long long int>]':
slon.cpp:424:15: required from here
slon.cpp:347:7: warning: unused variable 'pi' [-Wunused-variable]
347 | int pi=i;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
2 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
