闲话
魔圆要出新剧场版了！link
当然我一如既往地不会去自找刀吃的
老虚的刀 劲太足了
前几天看了 EI 的新博文
虽然很有旧基金会的感觉 但其实精神内核才是最重要的吧
共勉。
今日模拟赛
\(\text{T1 (connect)}\)
我们交换了近千条信息，感觉心的距离只近了一厘米。—— 《秒速五厘米》
可以发现不是两个端点都在边界上的线段等于不存在，因为我们可以贴着他的边绕过去。因此我们只需要考虑两端点都在边界上的线段。
这一部分有交当且仅当两条线段彼此交叉，也就是对于一条线段两端点截断的其中一个区域，存在一条线段有且仅有一个端点在其中。
这个可以将边界单独拿出来断成序列，在上面做类似括号序列的判定。
总时间复杂度 \(O(n \log n)\)，瓶颈在排序和离散化。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, w, t1, t2, t3, t4, fa[N], buk[N], stk[N], top;
vp vec;
struct __Hsh {
size_t operator() (const pii& __Pair) const {
return __Pair.first * 131 + __Pair.second;
}
}; unordered_map<pii, int, __Hsh> mp;
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
void merge(int u, int v) {
u = find(u), v = find(v);
fa[u] = v;
}
int get(pii x) {
if (x.first == 0) return x.second;
if (x.second == m) return x.first + m;
if (x.first == n) return m - x.second + m + n;
if (x.second == 0) return n - x.first + m + m + n;
return -1;
}
signed main() {
iot;
file(connect);
iota(fa, fa + N, 0);
cin >> n >> m >> w;
rep(i,1,w) {
cin >> t1 >> t2 >> t3 >> t4;
mp[{t1, t2}] = mp.size() + 1;
mp[{t3, t4}] = mp.size() + 1;
merge(mp.size(), mp.size() - 1);
if(t1 == 0 or t1 == n or t2 == 0 or t2 == m)
vec.eb(t1, t2);
if(t3 == 0 or t3 == n or t4 == 0 or t4 == m)
vec.eb(t3, t4);
}
sort(vec.begin(), vec.end(), [&](pii x, pii y) { return get(x) < get(y); });
for (auto v : vec) ++ buk[find(mp[v])];
for (auto v : vec) {
if (top and find(mp[v]) == stk[top]) -- buk[stk[top]];
else stk[++ top] = find(mp[v]);
if (top and buk[stk[top]] == 1) -- top;
}
top ? puts("NO") : puts("YES");
}
\(\text{T2 (liveon)}\)
Keep us deep down in your hearts and please keep living on - 《Living On》
简单树剖题。由经典数论结论可以知道我们可以把这一段的 \(a_i\) 乘起来，总体让 \(z\) 除。
这样我们就把原问题转化成了单点修改区间乘积了。熟悉一些经典问题的同学也可以知道，这里如果换成区间把值为 \(x\) 的元素改成 \(y\) 是可以做的，暴力的复杂度可以做到 \(\widetilde O(n\sqrt{n \log n})\)。挺劣的，有没有方法突破根号呢？
话题拉回来，这里有一个问题：一堆 \(a_i\) 的乘积很可能爆 long long，采用 double 存可能丢精度。这时又是经典转化，我们将 \(a_i\) 取 \(\log\) 用于和 \(z\) 比较大小。这样的精度是能保证的，而且当 \(\sum \log a_i \le \log z\) 时显然 \(\prod a_i\) 不会爆 long long。
这样我们就能在 \(O(n\log^2 n)\) 的复杂度内解决问题了。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, q, typ, t1, t2;
int dfn[N], idfn[N], iid[N], dep[N], son[N], siz[N], fa[N], top[N], stp;
ll t3, a[N];
vector<tuple<int,int,ll> > g[N];
struct dat {
ll prf; ld rec;
dat(ll prf = 1, ld rec = 0) : prf(prf), rec(rec) { }
dat operator * (const dat& b) { return { prf * b.prf, rec + b.rec }; }
};
struct SegmentCitrus {
#define ls (p << 1)
#define rs (p << 1 | 1)
#define prf(p) seg[p].prf
#define rec(p) seg[p].rec
dat seg[N << 2];
void build(int p = 1, int l = 1, int r = n) {
if (l == r) {
prf(p) = a[idfn[l]];
rec(p) = log2l(a[idfn[l]]);
return;
} int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
seg[p] = seg[ls] * seg[rs];
}
void upd(int p, int l, int r, int pos, ll v) {
if (l == r) {
prf(p) = v; rec(p) = log2l(v);
return ;
} int mid = l + r >> 1;
if (pos <= mid) upd(ls, l, mid, pos, v);
else upd(rs, mid + 1, r, pos, v);
seg[p] = seg[ls] * seg[rs];
}
dat query(int p, int l, int r, int L, int R) {
if (L > R) return dat();
if (L <= l and r <= R) return seg[p];
int mid = l + r >> 1; dat ret;
if (L <= mid) ret = ret * query(ls, l, mid, L, R);
if (mid < R) ret = ret * query(rs, mid + 1, r, L, R);
return ret;
}
} Tr;
void dfs1(int u, int fat) {
siz[u] = 1, son[u] = 0, fa[u] = fat;
dep[u] = dep[fat] + 1;
for (auto [v, w, id] : g[u]) if (v != fat) {
a[v] = w, iid[id] = v;
dfs1(v, u), siz[u] += siz[v];
if (siz[v] > siz[son[u]])
son[u] = v;
}
}
void dfs2(int u, int ctp) {
top[u] = ctp, dfn[u] = ++ stp, idfn[stp] = u;
if (son[u]) dfs2(son[u], ctp);
for (auto [v, w, id] : g[u]) if (v != fa[u] and v != son[u])
dfs2(v, v);
}
dat query(int u, int v) {
dat ret; if (u == v) return dat();
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = ret * Tr.query(1, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]];
} if (dep[u] > dep[v]) swap(u, v);
ret = ret * Tr.query(1, 1, n, dfn[u] + 1, dfn[v]);
return ret;
}
signed main() {
iot; file(liveon);
cin >> n >> q;
rep(i,1,n-1){
cin >> t1 >> t2 >> t3;
g[t1].eb(t2, t3, i);
g[t2].eb(t1, t3, i);
} dfs1(1, 0); dfs2(1, 1);
Tr.build();
while ( q -- ) {
cin >> typ >> t1 >> t2;
if (typ == 1) {
cin >> t3;
dat v = query(t1, t2);
if (v.rec > log2l(t3)) cout << 0 << '\n';
else cout << (t3 / v.prf) << '\n';
} else {
Tr.upd(1, 1, n, dfn[iid[t1]], t2);
}
}
}
\(\text{T3 (flower)}\)
飘飘然地 我们连声音也尽然忘却 —— 《偷春人》
对于这类问题，我们有一个经典的观察，就是提取两对的顺序关系，然后对原序列施这个偏序下的排序，就可以得到一种解法。因此我们观察 \(n = 2\) 的情况：
- \((1, 2), (3, 4)\)
这时定是无解的。 - \((1, 3), (2, 4)\)
我们需要两侧的大小变化是不同的，因此这一对必定翻转情况不同。 - \((1, 3), (2, 4)\)
同 \(2.\)，这一对必定翻转情况相同。 - \((1, 4), (2, 3)\)
这俩无关，不论如何都可以通过交换位置得到合法。
因此我们能建出 \(O(n^2)\) 条边的图，直接做 2-sat 的复杂度是 \(O(n^2)\) 的。
考虑优化。我们对 \(\min(a_i, b_i)\) 做排序，用一个 set 维护 \(\max(a_i ,b_i)\)，然后我们可以根据最小的 \(\max(a_i, b_i)\) 合并。容易发现这样会找到 \(O(n)\) 条有用的边，这些边能确定答案。
总时间复杂度 \(O(n\log n)\)。
其实没理解，我也不理解我贺的这份代码。
可以问 lyin 讲题解做法。
如何 \(O(n)\)？听说和这个做法完全不同。
code
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, other[N], t1, t2, ans;
struct pii {
int first, second;
bool operator < (const pii& b) const {
return first < b.first;
}
}; set<pii> st;
int calc() {
int tot = 1;
auto d = *st.begin();
int ans = d.second, r = other[d.first];
st.erase(st.begin()), st.erase({r, 0});
for (int ptr = 1; st.size(); ptr ^= 1) {
if (ptr) {
int r2 = 0;
while (st.size()) {
auto itr = -- st.end();
if (itr->first <= r) break;
tot ++, ans += itr->second;
int t1 = itr->first, t2 = other[t1];
if (t2 < r2 or t2 > r) return -1;
r2 = t2;
st.erase(itr), st.erase({t2, 0});
} if (r2 == 0) break;
r = r2;
} else {
int r2 = 1e9;
while (st.size()) {
auto itr = st.begin();
if (itr->first >= r) break;
tot ++, ans += itr->second;
int t1 = itr->first, t2 = other[t1];
if (t2 > r2 or t2 < r) return -1;
r2 = t2;
st.erase(itr), st.erase({t2, 0});
} if (r2 == 1e9) break;
r = r2;
}
} return min(ans, tot - ans);
}
signed main() {
iot; file(flower);
cin >> n;
rep(i,1,n) {
cin >> t1 >> t2;
other[t1] = t2, other[t2] = t1;
st.insert( { t1, 0 } ), st.insert( { t2, 1 } );
} while (st.size()) {
int now = calc();
if (now == -1) puts("-1"), exit(0);
ans += now;
} cout << ans << '\n';
}
\(\text{T4 (fantasy)}\)
幻想中 早已自封盖世英雄 无名无姓有神通 —— 《无理无智》
可能在 wlwz 里选这句的原因是这句最平凡？
考虑 DP。对于 DP 状态，我们总应当将一个币值拆分成许多更小的值，以此来生成方案。同时我们应当防止计数重复，因此不妨具体地将使用了几个值设计在状态之内。
我们设 \(f(i, x)\) 用于计数前 \(i\) 种货币凑出 \(m \bmod a_{i + 1} + x\times a_{i + 1}\) 的方案数，其中 \(i < n, x \ge 0\)。可以写出转移：
也就是枚举 \(a_i\) 的数量，\(j\) 的上界是 \(f(i - 1, x)\) 的第二维为 \(0\) 时的取值。
可以发现 \(f(i, x)\) 是以 \(x\) 为变量的 \(i - 1\) 次多项式，因为每次往下带入都是带入一个 \(x\) 相关的单项式后求和。因此我们维护 \(f(i, x)\) 对 \(x \in [0, i - 1]\) 的值，每次做前缀和后插值就能得到下一层的一个点值。具体地，对前缀和数组插出 \(\dfrac{m \bmod a_{i + 1}}{a_i} + \dfrac{x\times a_{i + 1}}{a_i}\) 处的值就是 \(f(i, x)\)。
最后 \(f(n - 1, m / a_n)\) 就是答案。
总时间复杂度 \(O(n^3)\)。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 100 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
// int mod;
const int mod = 1e6 + 3;
// const int mod = 469762049, g = 3;
// const int mod = 998244353; // const int g = 3;
// const int mod = 1004535809, g = 3;
// const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
// const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template<typename T1,typename T2>T1 add(T1 a,T2 b){return(a+=b)>=mod?a-mod:a;}template<typename T1,typename...Args>T1 add(T1 a,Args...b){return add(a,add(b...));}template<typename T1,typename T2>T1 sub(T1 a,T2 b){return(a-=b)<0?a+mod:a;}template<typename T1,typename...Args>T1 sub(T1 a,Args...b){return sub(a,add(b...));}template<typename T1,typename T2>void addi(T1&a,T2 b){(a+=b)>=mod?(a-=mod):true;}template<typename T1,typename...Args>void addi(T1&a,Args...b){addi(a,add(b...));}template<typename T1,typename T2>void subi(T1&a,T2 b){(a-=b)<0?(a+=mod):true;}template<typename T1,typename...Args>void subi(T1&a,Args...b){subi(a,add(b...));}
/* Fastmod / mul */ struct FastMod{int m;ll b;void init(int _m){m=_m;if(m==0)m=1;b=((lll)1<<64)/m;}FastMod(int _m){init(_m);}int operator()(ll a){ll q=((lll)a*b)>>64;a-=q*m;if(a>=m)a-=m;return a;}}Mod(mod);int mul(int a,int b){return Mod(1ll*a*b);}template<typename T1,typename T2>int mul(T1 a,T2 b){return Mod((long long)(1ll*a*b));}template<typename T,typename...Args>int mul(T a,Args...b){return mul(a,mul(b...));}template<typename T1,typename T2>void muli(T1&a,T2 b){a=Mod(1ll*a*b);}template<typename T1,typename...Args>void muli(T1&a,Args...b){muli(a,mul(b...));} // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp fac C */ template<typename T1,typename T2>T1 qp(T1 a,T2 b){T1 ret=1;for(;b>0;a=1ll*a*a%mod,b>>=1)if(b&1)ret=mul(ret,a);return ret;}vi __fac({1,1}),__ifc({1,1}),__inv({0,1});inline void ___prep(int n){static int i=2;if(i<n)for(__fac.resize(n),__ifc.resize(n),__inv.resize(n);i<n;i++)__fac[i]=mul(i,__fac[i-1]),__inv[i]=mul((mod-mod/i),__inv[mod%i]),__ifc[i]=mul(__inv[i],__ifc[i-1]);}inline int fac(int x){return ___prep(x+1),__fac[x];}inline int ifc(int x){return ___prep(x+1),__ifc[x];}inline int inv(int x){return ___prep(x+1),__inv[x];}inline int C(int n,int m){if(n<m or n<0 or m<0)return 0;return mul(fac(n),ifc(m),ifc(n-m));}
/* sum of i^k */ int S(int n,int k){vector<int>__pre(k+4),__suf(k+4),__pw(k+4),__pri(k+4);vector<bool>__vis(k+4,0);__pw[1]=1;for(int i=2,cnt=0;i<=k+2;++i){if(!__vis[i])__pri[++cnt]=i,__pw[i]=qp(i,k);for(int j=1;j<=cnt and i*__pri[j]<=k+2;++j){__vis[i*__pri[j]]=1;__pw[i*__pri[j]]=mul(__pw[i],__pw[__pri[j]]);if(i%__pri[j]==0)break;}}rep(i,2,k+2)__pw[i]=add(__pw[i],__pw[i-1]);__pre[0]=__suf[k+3]=1;rep(i,1,k+2)__pre[i]=mul(__pre[i-1],(n-i+mod));pre(i,k+2,1)__suf[i]=mul(__suf[i+1],(n-i+mod));int tmp=0,ret=0;rep(i,1,k+2){if((k-i)&1)subi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));else addi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));}return ret;}
// /* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1);
int n, ptr, ztr;
ll m, a[N], f[N][N];
ll lagr(int d, ll x, ll y[]) {
static ll pref[N], suff[N];
rep(i,0,d) pref[i] = mul(i ? pref[i - 1] : 1, sub(x, i));
pre(i,d,0) suff[i] = mul(i != d ? suff[i + 1] : 1, sub(x, i));
ll ret = 0, tmp;
rep(i,0,d) {
tmp = y[i];
if (i) tmp = mul(tmp, ifc(i), pref[i - 1]);
if (i != d) tmp = mul(tmp, ifc(d - i), d - i & 1 ? mod - 1 : 1, suff[i + 1]);
addi(ret, tmp);
} return ret;
}
signed main() {
file(fantasy);
cin >> n >> m;
rep(i,1,n) cin >> a[i];
if (m % a[1]) puts("0"), exit(0);
if (n == 1) puts("1"), exit(0);
rep(i,0,n-1) f[1][i] = 1;
rep(i,2,n-1) {
rep(j,1,i - 1) addi(f[i - 1][j], f[i - 1][j - 1]);
rep(j,0,i) f[i][j] = lagr(i - 1, (m % a[i + 1]) / a[i] + j * a[i + 1] / a[i], f[i - 1]);
} rep(i,1,n-1) addi(f[n - 1][i], f[n - 1][i - 1]);
cout << lagr(n - 1, m / a[n], f[n - 1]) << '\n';
}