[problem:1972A]↵
↵
<spoiler summary="Hint 1">↵
↵
Only add problems when they are needed.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1972A]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
//By: OIer rui_er↵
#include <bits/stdc++.h>↵
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)↵
#define per(x, y, z) for(int x = (y); x >= (z); --x)↵
#define endl '\n'↵
using namespace std;↵
typedef long long ll;↵
↵
const int N = 105;↵
↵
int T, n, a[N], b[N];↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0); cout.tie(0);↵
for(cin >> T; T; --T) {↵
cin >> n;↵
rep(i, 1, n) cin >> a[i];↵
rep(i, 1, n) cin >> b[i];↵
int diff = 0, ans = 0;↵
rep(i, 1, n) {↵
if(a[i - diff] > b[i]) {↵
++ans;↵
++diff;↵
}↵
}↵
cout << ans << endl;↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1972B]↵
↵
<spoiler summary="Hint 1">↵
↵
Is there anything that _never_ / _always_ changes after each operation?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
The parity.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1972B]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
//By: OIer rui_er↵
#include <bits/stdc++.h>↵
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)↵
#define per(x, y, z) for(int x = (y); x >= (z); --x)↵
#define endl '\n'↵
using namespace std;↵
typedef long long ll;↵
↵
int T, n;↵
string s;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0); cout.tie(0);↵
for(cin >> T; T; --T) {↵
cin >> n >> s;↵
int cntU = 0;↵
for(char c : s) if(c == 'U') ++cntU;↵
if(cntU & 1) cout << "YES" << endl;↵
else cout << "NO" << endl;↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967A]↵
↵
<spoiler summary="Hint 1">↵
↵
What's the answer if $a_1=a_2=\cdots=a_n$ and $k=0$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
What's the answer if $k=0$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
You've already known the $\mathcal O(k)$ solution. How to improve it?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967A]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
void solve()↵
{↵
int n;long long k;↵
cin>>n>>k;↵
vector<long long>a(n);↵
for(int x=0;x<n;x++)↵
cin>>a[x];↵
sort(a.begin(),a.end());↵
reverse(a.begin(),a.end());↵
long long lst=a.back(),cnt=1;↵
a.pop_back();↵
while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;↵
while(!a.empty())↵
{↵
long long delta=a.back()-lst;↵
if(k<delta*cnt)break;↵
k-=delta*cnt;↵
lst=a.back();↵
while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;↵
}↵
lst+=k/cnt;↵
k%=cnt;↵
cnt-=k;↵
cout<<lst*n-cnt+1<<endl;↵
}↵
main()↵
{↵
ios::sync_with_stdio(false),cin.tie(0);↵
int t;↵
cin>>t;↵
while(t--)solve();↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967B1]↵
↵
<spoiler summary="Hint 1">↵
↵
Denote $\gcd(a,b)$ as $d$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Did you notice that $b\mid a$? How to prove that?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967B1]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
const int N=2000005;↵
int tc,n,m; ll ans;↵
inline void solve(){↵
cin>>n>>m; ans=0;↵
for(int i=1;i<=m;i++)↵
ans+=(n+i)/(1ll*i*i);↵
cout<<ans-1<<'\n';↵
}↵
int main(){↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
cin>>tc; while(tc--) solve();↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967B2]↵
↵
<spoiler summary="Hint 1">↵
↵
Denote $\gcd(a,b)$ as $d$. Assume that $a=pd$ and $b=qd$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
$\gcd(p,q)=1$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
How large could $p$ and $q$ be?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967B2]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define nl "\n"↵
#define nf endl↵
#define ll long long↵
#define pb push_back↵
#define _ << ' ' <<↵
↵
#define INF (ll)1e18↵
#define mod 998244353↵
#define maxn 110↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
↵
#if !ONLINE_JUDGE && !EVAL↵
ifstream cin("input.txt");↵
ofstream cout("output.txt");↵
#endif↵
int t;↵
cin>>t;↵
while(t--)↵
{↵
ll n,m; cin >> n>>m;↵
ll sq = sqrt(n) + 2,sqm=sqrt(m)+2;↵
↵
vector bad(sq + 1, vector<bool>(sqm+1, 0));↵
for (ll i = 2; i <= min(sq,sqm); i++) {↵
for (ll a = i; a <= sq; a += i) {↵
for (ll b = i; b <= sqm; b += i) {↵
bad[a][b] = true;↵
}↵
}↵
}↵
↵
ll ans = 0;↵
for (ll a = 1; a * a <= n; a++) {↵
for (ll b = 1; b * b <= m; b++) {↵
if (bad[a][b]) continue;↵
ans += min(n/(a+b)/a,m/(a+b)/b);↵
}↵
}↵
cout << ans << nl;↵
}↵
↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967C]↵
↵
<spoiler summary="Hint 1">↵
↵
The height of a Fenwick Tree is $\mathcal O(\log n)$, so operations like enumerating ancestors of each vertex will be acceptable.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
What's the coefficient of $a_u$ in each $b$ value of its ancestors?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967C]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
//By: OIer rui_er↵
#include <bits/stdc++.h>↵
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)↵
#define per(x, y, z) for(int x = (y); x >= (z); --x)↵
#define debug(format...) fprintf(stderr, format)↵
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)↵
#define endl '\n'↵
using namespace std;↵
typedef long long ll;↵
↵
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());↵
int randint(int L, int R) {↵
uniform_int_distribution<int> dist(L, R);↵
return dist(rnd);↵
}↵
↵
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}↵
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}↵
↵
template<int mod>↵
inline unsigned int down(unsigned int x) {↵
return x >= mod ? x - mod : x;↵
}↵
↵
template<int mod>↵
struct Modint {↵
unsigned int x;↵
Modint() = default;↵
Modint(unsigned int x) : x(x) {}↵
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}↵
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}↵
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}↵
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}↵
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}↵
friend Modint operator/(Modint a, Modint b) {return a * ~b;}↵
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}↵
friend Modint operator~(Modint a) {return a ^ (mod - 2);}↵
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}↵
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}↵
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}↵
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}↵
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}↵
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}↵
friend Modint& operator++(Modint& a) {return a += 1;}↵
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}↵
friend Modint& operator--(Modint& a) {return a -= 1;}↵
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}↵
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}↵
friend bool operator!=(Modint a, Modint b) {return !(a == b);}↵
};↵
↵
const int N = 1e6 + 100, mod = 998244353;↵
typedef Modint<mod> mint;↵
↵
int T, n, k;↵
mint a[N], inv[N];↵
↵
inline int lowbit(int x) {return x & -x;}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0); cout.tie(0);↵
inv[0] = inv[1] = 1;↵
rep(i, 2, N - 1) inv[i] = (mod - mod / i) * inv[mod % i];↵
for(cin >> T; T; --T) {↵
cin >> n >> k;↵
rep(i, 1, n) cin >> a[i];↵
rep(i, 1, n) {↵
mint mul = 1;↵
for(int u = i + lowbit(i), d = 1; u <= n; u += lowbit(u), ++d) {↵
mul *= (d + k - 1) * inv[d];↵
a[u] -= mul * a[i];↵
}↵
}↵
rep(i, 1, n) cout << a[i] << " \n"[i == n];↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967D]↵
↵
<spoiler summary="Hint 1">↵
↵
Binary search on the answer of magics.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
You may come up with many $\mathcal O(m\log m + n\log^2 m)$ solutions with heavy data structures. Unfortunately, none of them is helpful.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
The key is to judge $\mathcal O(m\log n)$ times whether vertex $u$ is reachable from vertex $v$ in $k$ steps, instead of querying the minimal value or something else.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967D]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
namespace FastIO {↵
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }↵
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }↵
template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }↵
template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }↵
}; using namespace FastIO;↵
↵
#define MAXM 1000001↵
int dep[MAXM], id[MAXM], dfn[MAXM], to[MAXM], sz[MAXM], tot = 0;↵
std::vector<int> ch[MAXM];↵
void dfs(int u) {↵
sz[u] = 1, dfn[u] = ++tot;↵
for (int v : ch[u]) {↵
dep[v] = dep[u] + 1, id[v] = id[u];↵
dfs(v), sz[u] += sz[v];↵
}↵
}↵
inline bool inSub(int u, int v) /* v \in u ? */ { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + sz[u]; }↵
constexpr int INF = 0x3f3f3f3f;↵
inline int query(int u, int v) /* u -> v */ {↵
if (u == v) return 0;↵
if (id[u] != id[v]) return INF;↵
int res = INF;↵
if (inSub(v, u)) res = dep[u] - dep[v];↵
if (inSub(v, to[id[u]])) res = std::min(dep[u] - dep[v] + dep[to[id[u]]] + 1, res);↵
// printf("query(%d, %d) = %d\n", u, v, res);↵
return res;↵
}↵
↵
#define MAXN 1000001↵
int a[MAXN], N, M;↵
bool check(int val) {↵
// printf("check %d\n", val);↵
int lst = 1;↵
for (int i = 1; i <= N; ++i) {↵
while (lst <= M && query(a[i], lst) > val) ++lst;↵
if (lst > M) return false;↵
// printf("a[%d] = %d\n", i, lst); ↵
}↵
return true;↵
}↵
↵
namespace DSU {↵
int fa[MAXM];↵
void inis(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }↵
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }↵
inline bool merge(int x, int y) { if (find(x) == find(y)) return false; fa[fa[x]] = fa[y]; return true; }↵
}; using namespace DSU;↵
↵
int main() {↵
int T = read<int>();↵
while (T--) {↵
N = read<int>(), M = read<int>(), inis(M);↵
for (int i = 1; i <= N; ++i) a[i] = read<int>();↵
for (int x = 1; x <= M; ++x) dep[x] = id[x] = dfn[x] = to[x] = sz[x] = 0, ch[x].clear();↵
tot = 0;↵
for (int i = 1, p; i <= M; ++i) {↵
p = read<int>();↵
if (merge(i, p)) ch[p].push_back(i); else to[i] = p;↵
}↵
for (int i = 1; i <= M; ++i) if (to[i] > 0) id[i] = i, dfs(i);↵
if (!check(M)) { puts("-1"); continue; }↵
int L = 0, R = M;↵
while (L < R) {↵
int mid = L + R >> 1;↵
if (check(mid)) R = mid; else L = mid + 1;↵
}↵
print<int>(R, '\n');↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967E1]↵
↵
<spoiler summary="Hint 1">↵
↵
Use the simplest way to judge if an $a$ is valid.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
We've got a $\mathcal O(nm)$ solution. Our target time complexity is $\mathcal O(n\sqrt{n})$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
It can be boiled down to a grid path counting problem.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967E1]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
namespace FastIO {↵
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }↵
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }↵
template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }↵
template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }↵
}; using namespace FastIO;↵
↵
#define MAXN 2000001↵
namespace Maths {↵
constexpr int MOD = 998244353;↵
long long qpow(long long a, long long x) { long long ans = 1; while (x) (x & 1) && (ans = ans * a % MOD), a = a * a % MOD, x >>= 1; return ans; }↵
long long frac[MAXN << 1 | 1], prac[MAXN << 1 | 1];↵
inline void inis(int V = MAXN * 2) { frac[0] = prac[0] = 1; for (int i = 1; i <= V; ++i) frac[i] = frac[i - 1] * i % MOD; prac[V] = qpow(frac[V], MOD - 2); for (int i = V - 1; i; --i) prac[i] = prac[i + 1] * (i + 1) % MOD; }↵
inline long long C(int N, int M) { if (N < 0 || M < 0 || N < M) return 0; return frac[N] * prac[M] % MOD * prac[N - M] % MOD; }↵
}; using namespace Maths;↵
↵
struct Point {↵
int x, y;↵
Point () {}↵
Point (int X, int Y) : x(X), y(Y) {}↵
inline void flip(int b) { x += b, y -= b, std::swap(x, y); }↵
inline int calc() { return C(x + y, y); }↵
} pA, pB;↵
↵
inline void add(int& x, int y) { (x += y) >= MOD && (x -= MOD); }↵
inline void del(int& x, int y) { (x -= y) < 0 && (x += MOD); }↵
↵
int calc(int p, int q, int b1, int b2) {↵
pA = pB = Point(p, q);↵
int ans = pA.calc();↵
while (pA.x >= 0 && pA.y >= 0) ↵
pA.flip(b1), del(ans, pA.calc()), pA.flip(b2), add(ans, pA.calc());↵
while (pB.x >= 0 && pB.y >= 0) ↵
pB.flip(b2), del(ans, pB.calc()), pB.flip(b1), add(ans, pB.calc());↵
return ans;↵
}↵
↵
int dp[2][3001], powm[MAXN];↵
void solve() {↵
int N = read<int>(), M = read<int>(), b0 = read<int>();↵
if (b0 >= M) return (void)print<int>(qpow(M, N), '\n');↵
powm[0] = 1; for (int i = 1; i <= N; ++i) powm[i] = 1ll * M * powm[i - 1] % MOD;↵
if (1ll * M * M <= N) { // dp↵
for (int k = 0; k < M; ++k) dp[0][k] = (int)(k == b0), dp[1][k] = 0;↵
int ans = 1ll * dp[0][M - 1] * (M - 1) % MOD * powm[N - 1] % MOD;↵
for (int i = 1; i <= N; ++i) {↵
auto now = dp[i & 1], lst = dp[(i & 1) ^ 1];↵
now[0] = 0; for (int k = 0; k + 1 < M; ++k) now[k + 1] = 1ll * lst[k] * (M - 1) % MOD;↵
for (int k = 1; k < M; ++k) add(now[k - 1], lst[k]);↵
if (i < N) add(ans, 1ll * now[M - 1] * (M - 1) % MOD * powm[N - i - 1] % MOD);↵
}↵
for (int k = 0; k < M; ++k) add(ans, dp[N & 1][k]);↵
print<int>(ans, '\n');↵
} else { // reflective inclusion-exclusion↵
const int B1 = M - b0, B2 = -1 - b0; int ans = qpow(M, N);↵
for (int x = b0, y = 0, k = 1, p = b0; p < N; p += 2, ++x, ++y, k = 1ll * k * (M - 1) % MOD) ↵
del(ans, 1ll * calc(x, y, B1, B2) * k % MOD * powm[N - p - 1] % MOD);↵
print<int>(ans, '\n');↵
}↵
}↵
↵
int main() { int T = read<int>(); inis(); while (T--) solve(); return 0; }↵
```↵
↵
</spoiler>↵
↵
[problem:1967E2]↵
↵
Thanks [user:A_G,2024-04-30] for discovering that E2 is possible!↵
↵
<spoiler summary="Hint 1">↵
↵
Solve E1 with $\mathcal O(n\sqrt{n})$ solution first (The $\mathcal O(n\log^2n)$ solution doesn't help much in E2).↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
For a single round of inclusion-exclusion, write down the form of the answer as simple as possible.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967E2]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MOD = 998244353;↵
const int N = 2e6+5;↵
int inv[N];↵
↵
int inversemod(int p, int q) {↵
// assumes p > 0↵
// https://mirror.codeforces.com/blog/entry/23365↵
return (p > 1 ? q-1LL*inversemod(q%p, p)*q/p : 1);↵
}↵
↵
void add(int& x, int y) {↵
x += y;↵
if (x >= MOD) x -= MOD;↵
}↵
↵
void sub(int& x, int y) {↵
x -= y;↵
if (x < 0) x += MOD;↵
}↵
↵
int solve(int n, int m, int b0) {↵
// let X = hit -1, Y = hit m↵
// f(S) = count of sequences that end up in [0, infty] while containing the pattern S↵
// g(S) = count of sequences that end up in [-infty, -1] while containing the pattern S↵
// we want f() - f(X) + f(YX) - f(XYX) + f(YXYX) - f(XYXYX) + ...↵
// + g(Y) - g(XY) + g(YXY) - g(XYXY) + g(YXYXY) - ...↵
vector<int> pw(n+1);↵
pw[0] = 1;↵
for (int i = 1; i <= n; i++) pw[i] = 1LL*pw[i-1]*(m-1) % MOD;↵
↵
// final ans will be sum from i = 0 to n of (n choose i) a_i↵
vector<int> a(n+2);↵
auto work = [&] (int c, int pw_coeff, int sgn_x) -> bool {↵
// let RANGE = [-infty, -1] if sgn_x == -1 and [0, infty] if sgn_x == 1↵
// for all x in RANGE such that (n+x+c)/2 is between 0 and n inclusive,↵
// add pw_coeff*pw[(n+x-b0)/2] to a[(n+x+c)/2]↵
↵
// return 0 to signal that we are out of bounds and should exit, otherwise 1↵
int l = 0;↵
if (sgn_x == 1) l = max(l, (n+c+1)>>1);↵
int r = n;↵
if (sgn_x == -1) r = min(r, (n+c-1)>>1);↵
if (l > r) return 0;↵
add(a[l], 1LL*pw_coeff*pw[l-(b0+c)/2] % MOD);↵
sub(a[r+1], 1LL*pw_coeff*pw[r+1-(b0+c)/2] % MOD);↵
return 1;↵
};↵
↵
int ans = 0;↵
// f(k*YX)↵
// after reflection trick, end up in x + 2*(m+1)*k↵
for (int k = 0; work(2*(m+1)*k - b0, 1, 1); k++);↵
↵
// f(X + k*YX)↵
// after reflection trick, end up in -2-x - 2*(m+1)*k↵
for (int k = 0; work(2*(m+1)*k+2+b0, MOD-1, 1); k++);↵
↵
// g(Y + k*XY)↵
// after reflection trick, end up in 2*m-x + 2*(m+1)*k↵
for (int k = 0; work(-2*m -2*(m+1)*k + b0, 1, -1); k++);↵
↵
// g(k*XY)↵
// after reflection trick, end up in x - 2*(m+1)*k↵
for (int k = 1; work(-2*(m+1)*k - b0, MOD-1, -1); k++);↵
↵
for (int i = 1; i <= n; i++) {↵
add(a[i], 1LL*a[i-1]*(m-1) % MOD);↵
}↵
↵
// do the binomial stuff without precalculated factorials because why not↵
int coeff = 1;↵
for (int i = 0; i <= n; i++) {↵
add(ans, 1LL * coeff * a[i] % MOD);↵
coeff = 1LL * coeff * (n-i) % MOD * inv[i+1] % MOD;↵
}↵
↵
return ans;↵
}↵
↵
int main () {↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
inv[1] = 1;↵
for (int i = 2; i < N; i++) inv[i] = 1LL*(MOD-MOD/i)*inv[MOD % i] % MOD;↵
↵
int T;↵
cin >> T;↵
while (T--) {↵
int n, m, b0;↵
cin >> n >> m >> b0;↵
if (b0 >= m) {↵
int ans = 1;↵
for (int i = 0; i < n; i++) ans = 1LL*ans*m % MOD;↵
cout << ans << '\n';↵
continue;↵
}↵
cout << solve(n, m, b0) << '\n';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967F]↵
↵
<spoiler summary="Hint 1">↵
↵
How to maintain $\sum\min(nxt_i-pre_i,x)$? Try $\sum\min(nxt_i-i,x)+\min(i-pre_i,x)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
To maintain $\sum\min(nxt_i-i,x)$, we can use chunking. Just +1 and $\operatorname{chkmin}$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
To finish it, consider what we do in segment-beats.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967F]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
constexpr int maxn=300010,maxq=100010,B=400;↵
↵
int n,bn,a[maxn],b[maxn],idx[maxn],nxt[maxn],add[maxn/B+5],mxadd[maxn/B+5],mx[maxn/B+5],se[maxn/B+5],t[maxn];↵
long long ans[maxq];↵
vector<int>val[maxn/B+5],mxval[maxn/B+5],pre[maxn/B+5],mxpre[maxn/B+5],pos[maxn/B+5],ks[maxn];↵
↵
void vAdd(int i)↵
{↵
for(;i<=n;i+=(i&-i)) t[i]++;↵
}↵
↵
int nQuery(int i)↵
{↵
int s=0;↵
for(;i;i-=(i&-i)) s+=t[i];↵
return s;↵
}↵
↵
void vWork()↵
{↵
int i,j,tot=0;↵
for(i=1;i<=n;i++) b[a[i]]=i;↵
for(i=1;i<=n;i++)↵
{↵
int p=b[i],bp=(p-1)/B+1;↵
val[bp].clear();↵
mxval[bp].clear();↵
auto radixsort=[](vector<int>&v)↵
{↵
if(v.empty()) return;↵
static int buc[1024],res[B+5];↵
auto tmp=minmax_element(v.begin(),v.end());↵
int mn=*tmp.first,rg=*tmp.second-mn;↵
if(!rg) return;↵
int lv=__lg(rg)/2+1,len=1<<lv,i;↵
memset(buc,0,len*4);↵
for(int &it:v) it-=mn,buc[it&(len-1)]++;↵
for(i=1;i<len;i++) buc[i]+=buc[i-1];↵
for(int it:v) res[--buc[it&(len-1)]]=it;↵
memset(buc,0,len*4);↵
for(int it:v) buc[it>>lv]++;↵
for(i=1;i<len;i++) buc[i]+=buc[i-1];↵
for(i=v.size()-1;i>=0;i--) v[--buc[res[i]>>lv]]=res[i]+mn;↵
};↵
auto getpre=[&](vector<int>&pre,const vector<int>&ori)↵
{↵
pre.resize(ori.size());↵
if(ori.empty()) return;↵
pre[0]=ori[0];↵
for(int i=1;i<(int)ori.size();i++) pre[i]=pre[i-1]+ori[i];↵
};↵
int lstmx=mx[bp];↵
vAdd(p);↵
idx[p]=nQuery(p);↵
mx[bp]=nxt[p]=n*2;↵
se[bp]=0;↵
auto it=pos[bp].begin();↵
for(;it<pos[bp].end();it++)↵
{↵
j=*it;↵
if(j>p) break;↵
nxt[j]+=add[bp];↵
if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];↵
nxt[j]=min(nxt[j],idx[p]);↵
idx[j]+=add[bp];↵
if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];↵
else if(nxt[j]>se[bp]) se[bp]=nxt[j];↵
}↵
it=pos[bp].insert(it,p);↵
for(it++;it!=pos[bp].end();it++)↵
{↵
j=*it;↵
nxt[j]+=add[bp];↵
if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];↵
nxt[j]++;↵
idx[j]+=add[bp]+1;↵
if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];↵
else if(nxt[j]>se[bp]) se[bp]=nxt[j];↵
}↵
for(int j:pos[bp])↵
{↵
if(nxt[j]==mx[bp]) mxval[bp].push_back(nxt[j]-idx[j]);↵
else val[bp].push_back(nxt[j]-idx[j]);↵
}↵
add[bp]=mxadd[bp]=0;↵
radixsort(val[bp]);↵
getpre(pre[bp],val[bp]);↵
radixsort(mxval[bp]);↵
getpre(mxpre[bp],mxval[bp]);↵
for(j=bp+1;j<=bn;j++) add[j]++,mx[j]++,se[j]++;↵
for(j=1;j<bp;j++)↵
{↵
if(mx[j]<=idx[p]) continue;↵
if(se[j]<idx[p])↵
{↵
mxadd[j]+=idx[p]-mx[j],mx[j]=idx[p];↵
continue;↵
}↵
val[j].clear();↵
mxval[j].clear();↵
lstmx=mx[j];↵
mx[j]=idx[p],se[j]=0;↵
for(int x:pos[j])↵
{↵
nxt[x]+=add[j];↵
idx[x]+=add[j];↵
if(nxt[x]>lstmx) nxt[x]+=mxadd[j];↵
if(nxt[x]>=idx[p])↵
{↵
nxt[x]=idx[p];↵
mxval[j].push_back(nxt[x]-idx[x]);↵
}↵
else↵
{↵
if(nxt[x]>se[j]) se[j]=nxt[x];↵
val[j].push_back(nxt[x]-idx[x]);↵
}↵
}↵
add[j]=mxadd[j]=0;↵
radixsort(val[j]);↵
getpre(pre[j],val[j]);↵
radixsort(mxval[j]);↵
getpre(mxpre[j],mxval[j]);↵
}↵
for(int ki:ks[i])↵
{↵
tot++;↵
for(j=1;j<=bn;j++)↵
{↵
auto it=lower_bound(val[j].begin(),val[j].end(),ki);↵
ans[tot]+=(val[j].end()-it)*ki;↵
if(it!=val[j].begin()) ans[tot]+=pre[j][it-val[j].begin()-1];↵
it=lower_bound(mxval[j].begin(),mxval[j].end(),ki-mxadd[j]);↵
ans[tot]+=(mxval[j].end()-it)*ki;↵
if(it!=mxval[j].begin()) ans[tot]+=(it-mxval[j].begin())*mxadd[j]+mxpre[j][it-mxval[j].begin()-1];↵
}↵
}↵
}↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(false),cin.tie(0);↵
int T;↵
cin>>T;↵
while(T--)↵
{↵
int i,ki,tot=0;↵
cin>>n;↵
bn=(n-1)/B+1;↵
for(i=1;i<=n;i++) cin>>a[i];↵
for(i=1;i<=n;i++)↵
{↵
cin>>ki;↵
ks[i].resize(ki);↵
for(int &it:ks[i])↵
{↵
cin>>it;↵
ans[++tot]=-(i+it-1);↵
}↵
}↵
vWork();↵
reverse(a+1,a+n+1);↵
for(int x=1;x<=n;x++)↵
t[x]=0;↵
for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();↵
vWork();↵
for(int x=1;x<=n;x++)↵
t[x]=0;↵
for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();↵
for(i=1;i<=tot;i++) cout<<ans[i]<<'\n';↵
tot=0;↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
↵
Only add problems when they are needed.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1972A]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
//By: OIer rui_er↵
#include <bits/stdc++.h>↵
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)↵
#define per(x, y, z) for(int x = (y); x >= (z); --x)↵
#define endl '\n'↵
using namespace std;↵
typedef long long ll;↵
↵
const int N = 105;↵
↵
int T, n, a[N], b[N];↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0); cout.tie(0);↵
for(cin >> T; T; --T) {↵
cin >> n;↵
rep(i, 1, n) cin >> a[i];↵
rep(i, 1, n) cin >> b[i];↵
int diff = 0, ans = 0;↵
rep(i, 1, n) {↵
if(a[i - diff] > b[i]) {↵
++ans;↵
++diff;↵
}↵
}↵
cout << ans << endl;↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1972B]↵
↵
<spoiler summary="Hint 1">↵
↵
Is there anything that _never_ / _always_ changes after each operation?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
The parity.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1972B]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
//By: OIer rui_er↵
#include <bits/stdc++.h>↵
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)↵
#define per(x, y, z) for(int x = (y); x >= (z); --x)↵
#define endl '\n'↵
using namespace std;↵
typedef long long ll;↵
↵
int T, n;↵
string s;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0); cout.tie(0);↵
for(cin >> T; T; --T) {↵
cin >> n >> s;↵
int cntU = 0;↵
for(char c : s) if(c == 'U') ++cntU;↵
if(cntU & 1) cout << "YES" << endl;↵
else cout << "NO" << endl;↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967A]↵
↵
<spoiler summary="Hint 1">↵
↵
What's the answer if $a_1=a_2=\cdots=a_n$ and $k=0$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
What's the answer if $k=0$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
You've already known the $\mathcal O(k)$ solution. How to improve it?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967A]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
void solve()↵
{↵
int n;long long k;↵
cin>>n>>k;↵
vector<long long>a(n);↵
for(int x=0;x<n;x++)↵
cin>>a[x];↵
sort(a.begin(),a.end());↵
reverse(a.begin(),a.end());↵
long long lst=a.back(),cnt=1;↵
a.pop_back();↵
while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;↵
while(!a.empty())↵
{↵
long long delta=a.back()-lst;↵
if(k<delta*cnt)break;↵
k-=delta*cnt;↵
lst=a.back();↵
while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;↵
}↵
lst+=k/cnt;↵
k%=cnt;↵
cnt-=k;↵
cout<<lst*n-cnt+1<<endl;↵
}↵
main()↵
{↵
ios::sync_with_stdio(false),cin.tie(0);↵
int t;↵
cin>>t;↵
while(t--)solve();↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967B1]↵
↵
<spoiler summary="Hint 1">↵
↵
Denote $\gcd(a,b)$ as $d$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Did you notice that $b\mid a$? How to prove that?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967B1]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
const int N=2000005;↵
int tc,n,m; ll ans;↵
inline void solve(){↵
cin>>n>>m; ans=0;↵
for(int i=1;i<=m;i++)↵
ans+=(n+i)/(1ll*i*i);↵
cout<<ans-1<<'\n';↵
}↵
int main(){↵
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
cin>>tc; while(tc--) solve();↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967B2]↵
↵
<spoiler summary="Hint 1">↵
↵
Denote $\gcd(a,b)$ as $d$. Assume that $a=pd$ and $b=qd$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
$\gcd(p,q)=1$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
How large could $p$ and $q$ be?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967B2]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define nl "\n"↵
#define nf endl↵
#define ll long long↵
#define pb push_back↵
#define _ << ' ' <<↵
↵
#define INF (ll)1e18↵
#define mod 998244353↵
#define maxn 110↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
↵
#if !ONLINE_JUDGE && !EVAL↵
ifstream cin("input.txt");↵
ofstream cout("output.txt");↵
#endif↵
int t;↵
cin>>t;↵
while(t--)↵
{↵
ll n,m; cin >> n>>m;↵
ll sq = sqrt(n) + 2,sqm=sqrt(m)+2;↵
↵
vector bad(sq + 1, vector<bool>(sqm+1, 0));↵
for (ll i = 2; i <= min(sq,sqm); i++) {↵
for (ll a = i; a <= sq; a += i) {↵
for (ll b = i; b <= sqm; b += i) {↵
bad[a][b] = true;↵
}↵
}↵
}↵
↵
ll ans = 0;↵
for (ll a = 1; a * a <= n; a++) {↵
for (ll b = 1; b * b <= m; b++) {↵
if (bad[a][b]) continue;↵
ans += min(n/(a+b)/a,m/(a+b)/b);↵
}↵
}↵
cout << ans << nl;↵
}↵
↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967C]↵
↵
<spoiler summary="Hint 1">↵
↵
The height of a Fenwick Tree is $\mathcal O(\log n)$, so operations like enumerating ancestors of each vertex will be acceptable.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
What's the coefficient of $a_u$ in each $b$ value of its ancestors?↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967C]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
//By: OIer rui_er↵
#include <bits/stdc++.h>↵
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)↵
#define per(x, y, z) for(int x = (y); x >= (z); --x)↵
#define debug(format...) fprintf(stderr, format)↵
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)↵
#define endl '\n'↵
using namespace std;↵
typedef long long ll;↵
↵
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());↵
int randint(int L, int R) {↵
uniform_int_distribution<int> dist(L, R);↵
return dist(rnd);↵
}↵
↵
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}↵
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}↵
↵
template<int mod>↵
inline unsigned int down(unsigned int x) {↵
return x >= mod ? x - mod : x;↵
}↵
↵
template<int mod>↵
struct Modint {↵
unsigned int x;↵
Modint() = default;↵
Modint(unsigned int x) : x(x) {}↵
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}↵
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}↵
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}↵
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}↵
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}↵
friend Modint operator/(Modint a, Modint b) {return a * ~b;}↵
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}↵
friend Modint operator~(Modint a) {return a ^ (mod - 2);}↵
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}↵
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}↵
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}↵
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}↵
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}↵
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}↵
friend Modint& operator++(Modint& a) {return a += 1;}↵
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}↵
friend Modint& operator--(Modint& a) {return a -= 1;}↵
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}↵
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}↵
friend bool operator!=(Modint a, Modint b) {return !(a == b);}↵
};↵
↵
const int N = 1e6 + 100, mod = 998244353;↵
typedef Modint<mod> mint;↵
↵
int T, n, k;↵
mint a[N], inv[N];↵
↵
inline int lowbit(int x) {return x & -x;}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0); cout.tie(0);↵
inv[0] = inv[1] = 1;↵
rep(i, 2, N - 1) inv[i] = (mod - mod / i) * inv[mod % i];↵
for(cin >> T; T; --T) {↵
cin >> n >> k;↵
rep(i, 1, n) cin >> a[i];↵
rep(i, 1, n) {↵
mint mul = 1;↵
for(int u = i + lowbit(i), d = 1; u <= n; u += lowbit(u), ++d) {↵
mul *= (d + k - 1) * inv[d];↵
a[u] -= mul * a[i];↵
}↵
}↵
rep(i, 1, n) cout << a[i] << " \n"[i == n];↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967D]↵
↵
<spoiler summary="Hint 1">↵
↵
Binary search on the answer of magics.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
You may come up with many $\mathcal O(m\log m + n\log^2 m)$ solutions with heavy data structures. Unfortunately, none of them is helpful.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
The key is to judge $\mathcal O(m\log n)$ times whether vertex $u$ is reachable from vertex $v$ in $k$ steps, instead of querying the minimal value or something else.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967D]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
namespace FastIO {↵
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }↵
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }↵
template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }↵
template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }↵
}; using namespace FastIO;↵
↵
#define MAXM 1000001↵
int dep[MAXM], id[MAXM], dfn[MAXM], to[MAXM], sz[MAXM], tot = 0;↵
std::vector<int> ch[MAXM];↵
void dfs(int u) {↵
sz[u] = 1, dfn[u] = ++tot;↵
for (int v : ch[u]) {↵
dep[v] = dep[u] + 1, id[v] = id[u];↵
dfs(v), sz[u] += sz[v];↵
}↵
}↵
inline bool inSub(int u, int v) /* v \in u ? */ { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + sz[u]; }↵
constexpr int INF = 0x3f3f3f3f;↵
inline int query(int u, int v) /* u -> v */ {↵
if (u == v) return 0;↵
if (id[u] != id[v]) return INF;↵
int res = INF;↵
if (inSub(v, u)) res = dep[u] - dep[v];↵
if (inSub(v, to[id[u]])) res = std::min(dep[u] - dep[v] + dep[to[id[u]]] + 1, res);↵
// printf("query(%d, %d) = %d\n", u, v, res);↵
return res;↵
}↵
↵
#define MAXN 1000001↵
int a[MAXN], N, M;↵
bool check(int val) {↵
// printf("check %d\n", val);↵
int lst = 1;↵
for (int i = 1; i <= N; ++i) {↵
while (lst <= M && query(a[i], lst) > val) ++lst;↵
if (lst > M) return false;↵
// printf("a[%d] = %d\n", i, lst); ↵
}↵
return true;↵
}↵
↵
namespace DSU {↵
int fa[MAXM];↵
void inis(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }↵
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }↵
inline bool merge(int x, int y) { if (find(x) == find(y)) return false; fa[fa[x]] = fa[y]; return true; }↵
}; using namespace DSU;↵
↵
int main() {↵
int T = read<int>();↵
while (T--) {↵
N = read<int>(), M = read<int>(), inis(M);↵
for (int i = 1; i <= N; ++i) a[i] = read<int>();↵
for (int x = 1; x <= M; ++x) dep[x] = id[x] = dfn[x] = to[x] = sz[x] = 0, ch[x].clear();↵
tot = 0;↵
for (int i = 1, p; i <= M; ++i) {↵
p = read<int>();↵
if (merge(i, p)) ch[p].push_back(i); else to[i] = p;↵
}↵
for (int i = 1; i <= M; ++i) if (to[i] > 0) id[i] = i, dfs(i);↵
if (!check(M)) { puts("-1"); continue; }↵
int L = 0, R = M;↵
while (L < R) {↵
int mid = L + R >> 1;↵
if (check(mid)) R = mid; else L = mid + 1;↵
}↵
print<int>(R, '\n');↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967E1]↵
↵
<spoiler summary="Hint 1">↵
↵
Use the simplest way to judge if an $a$ is valid.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
We've got a $\mathcal O(nm)$ solution. Our target time complexity is $\mathcal O(n\sqrt{n})$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
It can be boiled down to a grid path counting problem.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967E1]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
↵
namespace FastIO {↵
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }↵
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }↵
template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }↵
template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }↵
}; using namespace FastIO;↵
↵
#define MAXN 2000001↵
namespace Maths {↵
constexpr int MOD = 998244353;↵
long long qpow(long long a, long long x) { long long ans = 1; while (x) (x & 1) && (ans = ans * a % MOD), a = a * a % MOD, x >>= 1; return ans; }↵
long long frac[MAXN << 1 | 1], prac[MAXN << 1 | 1];↵
inline void inis(int V = MAXN * 2) { frac[0] = prac[0] = 1; for (int i = 1; i <= V; ++i) frac[i] = frac[i - 1] * i % MOD; prac[V] = qpow(frac[V], MOD - 2); for (int i = V - 1; i; --i) prac[i] = prac[i + 1] * (i + 1) % MOD; }↵
inline long long C(int N, int M) { if (N < 0 || M < 0 || N < M) return 0; return frac[N] * prac[M] % MOD * prac[N - M] % MOD; }↵
}; using namespace Maths;↵
↵
struct Point {↵
int x, y;↵
Point () {}↵
Point (int X, int Y) : x(X), y(Y) {}↵
inline void flip(int b) { x += b, y -= b, std::swap(x, y); }↵
inline int calc() { return C(x + y, y); }↵
} pA, pB;↵
↵
inline void add(int& x, int y) { (x += y) >= MOD && (x -= MOD); }↵
inline void del(int& x, int y) { (x -= y) < 0 && (x += MOD); }↵
↵
int calc(int p, int q, int b1, int b2) {↵
pA = pB = Point(p, q);↵
int ans = pA.calc();↵
while (pA.x >= 0 && pA.y >= 0) ↵
pA.flip(b1), del(ans, pA.calc()), pA.flip(b2), add(ans, pA.calc());↵
while (pB.x >= 0 && pB.y >= 0) ↵
pB.flip(b2), del(ans, pB.calc()), pB.flip(b1), add(ans, pB.calc());↵
return ans;↵
}↵
↵
int dp[2][3001], powm[MAXN];↵
void solve() {↵
int N = read<int>(), M = read<int>(), b0 = read<int>();↵
if (b0 >= M) return (void)print<int>(qpow(M, N), '\n');↵
powm[0] = 1; for (int i = 1; i <= N; ++i) powm[i] = 1ll * M * powm[i - 1] % MOD;↵
if (1ll * M * M <= N) { // dp↵
for (int k = 0; k < M; ++k) dp[0][k] = (int)(k == b0), dp[1][k] = 0;↵
int ans = 1ll * dp[0][M - 1] * (M - 1) % MOD * powm[N - 1] % MOD;↵
for (int i = 1; i <= N; ++i) {↵
auto now = dp[i & 1], lst = dp[(i & 1) ^ 1];↵
now[0] = 0; for (int k = 0; k + 1 < M; ++k) now[k + 1] = 1ll * lst[k] * (M - 1) % MOD;↵
for (int k = 1; k < M; ++k) add(now[k - 1], lst[k]);↵
if (i < N) add(ans, 1ll * now[M - 1] * (M - 1) % MOD * powm[N - i - 1] % MOD);↵
}↵
for (int k = 0; k < M; ++k) add(ans, dp[N & 1][k]);↵
print<int>(ans, '\n');↵
} else { // reflective inclusion-exclusion↵
const int B1 = M - b0, B2 = -1 - b0; int ans = qpow(M, N);↵
for (int x = b0, y = 0, k = 1, p = b0; p < N; p += 2, ++x, ++y, k = 1ll * k * (M - 1) % MOD) ↵
del(ans, 1ll * calc(x, y, B1, B2) * k % MOD * powm[N - p - 1] % MOD);↵
print<int>(ans, '\n');↵
}↵
}↵
↵
int main() { int T = read<int>(); inis(); while (T--) solve(); return 0; }↵
```↵
↵
</spoiler>↵
↵
[problem:1967E2]↵
↵
Thanks [user:A_G,2024-04-30] for discovering that E2 is possible!↵
↵
<spoiler summary="Hint 1">↵
↵
Solve E1 with $\mathcal O(n\sqrt{n})$ solution first (The $\mathcal O(n\log^2n)$ solution doesn't help much in E2).↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
For a single round of inclusion-exclusion, write down the form of the answer as simple as possible.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967E2]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MOD = 998244353;↵
const int N = 2e6+5;↵
int inv[N];↵
↵
int inversemod(int p, int q) {↵
// assumes p > 0↵
// https://mirror.codeforces.com/blog/entry/23365↵
return (p > 1 ? q-1LL*inversemod(q%p, p)*q/p : 1);↵
}↵
↵
void add(int& x, int y) {↵
x += y;↵
if (x >= MOD) x -= MOD;↵
}↵
↵
void sub(int& x, int y) {↵
x -= y;↵
if (x < 0) x += MOD;↵
}↵
↵
int solve(int n, int m, int b0) {↵
// let X = hit -1, Y = hit m↵
// f(S) = count of sequences that end up in [0, infty] while containing the pattern S↵
// g(S) = count of sequences that end up in [-infty, -1] while containing the pattern S↵
// we want f() - f(X) + f(YX) - f(XYX) + f(YXYX) - f(XYXYX) + ...↵
// + g(Y) - g(XY) + g(YXY) - g(XYXY) + g(YXYXY) - ...↵
vector<int> pw(n+1);↵
pw[0] = 1;↵
for (int i = 1; i <= n; i++) pw[i] = 1LL*pw[i-1]*(m-1) % MOD;↵
↵
// final ans will be sum from i = 0 to n of (n choose i) a_i↵
vector<int> a(n+2);↵
auto work = [&] (int c, int pw_coeff, int sgn_x) -> bool {↵
// let RANGE = [-infty, -1] if sgn_x == -1 and [0, infty] if sgn_x == 1↵
// for all x in RANGE such that (n+x+c)/2 is between 0 and n inclusive,↵
// add pw_coeff*pw[(n+x-b0)/2] to a[(n+x+c)/2]↵
↵
// return 0 to signal that we are out of bounds and should exit, otherwise 1↵
int l = 0;↵
if (sgn_x == 1) l = max(l, (n+c+1)>>1);↵
int r = n;↵
if (sgn_x == -1) r = min(r, (n+c-1)>>1);↵
if (l > r) return 0;↵
add(a[l], 1LL*pw_coeff*pw[l-(b0+c)/2] % MOD);↵
sub(a[r+1], 1LL*pw_coeff*pw[r+1-(b0+c)/2] % MOD);↵
return 1;↵
};↵
↵
int ans = 0;↵
// f(k*YX)↵
// after reflection trick, end up in x + 2*(m+1)*k↵
for (int k = 0; work(2*(m+1)*k - b0, 1, 1); k++);↵
↵
// f(X + k*YX)↵
// after reflection trick, end up in -2-x - 2*(m+1)*k↵
for (int k = 0; work(2*(m+1)*k+2+b0, MOD-1, 1); k++);↵
↵
// g(Y + k*XY)↵
// after reflection trick, end up in 2*m-x + 2*(m+1)*k↵
for (int k = 0; work(-2*m -2*(m+1)*k + b0, 1, -1); k++);↵
↵
// g(k*XY)↵
// after reflection trick, end up in x - 2*(m+1)*k↵
for (int k = 1; work(-2*(m+1)*k - b0, MOD-1, -1); k++);↵
↵
for (int i = 1; i <= n; i++) {↵
add(a[i], 1LL*a[i-1]*(m-1) % MOD);↵
}↵
↵
// do the binomial stuff without precalculated factorials because why not↵
int coeff = 1;↵
for (int i = 0; i <= n; i++) {↵
add(ans, 1LL * coeff * a[i] % MOD);↵
coeff = 1LL * coeff * (n-i) % MOD * inv[i+1] % MOD;↵
}↵
↵
return ans;↵
}↵
↵
int main () {↵
ios_base::sync_with_stdio(0); cin.tie(0);↵
inv[1] = 1;↵
for (int i = 2; i < N; i++) inv[i] = 1LL*(MOD-MOD/i)*inv[MOD % i] % MOD;↵
↵
int T;↵
cin >> T;↵
while (T--) {↵
int n, m, b0;↵
cin >> n >> m >> b0;↵
if (b0 >= m) {↵
int ans = 1;↵
for (int i = 0; i < n; i++) ans = 1LL*ans*m % MOD;↵
cout << ans << '\n';↵
continue;↵
}↵
cout << solve(n, m, b0) << '\n';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
[problem:1967F]↵
↵
<spoiler summary="Hint 1">↵
↵
How to maintain $\sum\min(nxt_i-pre_i,x)$? Try $\sum\min(nxt_i-i,x)+\min(i-pre_i,x)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
To maintain $\sum\min(nxt_i-i,x)$, we can use chunking. Just +1 and $\operatorname{chkmin}$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
To finish it, consider what we do in segment-beats.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
[tutorial:1967F]↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
```cpp↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
constexpr int maxn=300010,maxq=100010,B=400;↵
↵
int n,bn,a[maxn],b[maxn],idx[maxn],nxt[maxn],add[maxn/B+5],mxadd[maxn/B+5],mx[maxn/B+5],se[maxn/B+5],t[maxn];↵
long long ans[maxq];↵
vector<int>val[maxn/B+5],mxval[maxn/B+5],pre[maxn/B+5],mxpre[maxn/B+5],pos[maxn/B+5],ks[maxn];↵
↵
void vAdd(int i)↵
{↵
for(;i<=n;i+=(i&-i)) t[i]++;↵
}↵
↵
int nQuery(int i)↵
{↵
int s=0;↵
for(;i;i-=(i&-i)) s+=t[i];↵
return s;↵
}↵
↵
void vWork()↵
{↵
int i,j,tot=0;↵
for(i=1;i<=n;i++) b[a[i]]=i;↵
for(i=1;i<=n;i++)↵
{↵
int p=b[i],bp=(p-1)/B+1;↵
val[bp].clear();↵
mxval[bp].clear();↵
auto radixsort=[](vector<int>&v)↵
{↵
if(v.empty()) return;↵
static int buc[1024],res[B+5];↵
auto tmp=minmax_element(v.begin(),v.end());↵
int mn=*tmp.first,rg=*tmp.second-mn;↵
if(!rg) return;↵
int lv=__lg(rg)/2+1,len=1<<lv,i;↵
memset(buc,0,len*4);↵
for(int &it:v) it-=mn,buc[it&(len-1)]++;↵
for(i=1;i<len;i++) buc[i]+=buc[i-1];↵
for(int it:v) res[--buc[it&(len-1)]]=it;↵
memset(buc,0,len*4);↵
for(int it:v) buc[it>>lv]++;↵
for(i=1;i<len;i++) buc[i]+=buc[i-1];↵
for(i=v.size()-1;i>=0;i--) v[--buc[res[i]>>lv]]=res[i]+mn;↵
};↵
auto getpre=[&](vector<int>&pre,const vector<int>&ori)↵
{↵
pre.resize(ori.size());↵
if(ori.empty()) return;↵
pre[0]=ori[0];↵
for(int i=1;i<(int)ori.size();i++) pre[i]=pre[i-1]+ori[i];↵
};↵
int lstmx=mx[bp];↵
vAdd(p);↵
idx[p]=nQuery(p);↵
mx[bp]=nxt[p]=n*2;↵
se[bp]=0;↵
auto it=pos[bp].begin();↵
for(;it<pos[bp].end();it++)↵
{↵
j=*it;↵
if(j>p) break;↵
nxt[j]+=add[bp];↵
if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];↵
nxt[j]=min(nxt[j],idx[p]);↵
idx[j]+=add[bp];↵
if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];↵
else if(nxt[j]>se[bp]) se[bp]=nxt[j];↵
}↵
it=pos[bp].insert(it,p);↵
for(it++;it!=pos[bp].end();it++)↵
{↵
j=*it;↵
nxt[j]+=add[bp];↵
if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];↵
nxt[j]++;↵
idx[j]+=add[bp]+1;↵
if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];↵
else if(nxt[j]>se[bp]) se[bp]=nxt[j];↵
}↵
for(int j:pos[bp])↵
{↵
if(nxt[j]==mx[bp]) mxval[bp].push_back(nxt[j]-idx[j]);↵
else val[bp].push_back(nxt[j]-idx[j]);↵
}↵
add[bp]=mxadd[bp]=0;↵
radixsort(val[bp]);↵
getpre(pre[bp],val[bp]);↵
radixsort(mxval[bp]);↵
getpre(mxpre[bp],mxval[bp]);↵
for(j=bp+1;j<=bn;j++) add[j]++,mx[j]++,se[j]++;↵
for(j=1;j<bp;j++)↵
{↵
if(mx[j]<=idx[p]) continue;↵
if(se[j]<idx[p])↵
{↵
mxadd[j]+=idx[p]-mx[j],mx[j]=idx[p];↵
continue;↵
}↵
val[j].clear();↵
mxval[j].clear();↵
lstmx=mx[j];↵
mx[j]=idx[p],se[j]=0;↵
for(int x:pos[j])↵
{↵
nxt[x]+=add[j];↵
idx[x]+=add[j];↵
if(nxt[x]>lstmx) nxt[x]+=mxadd[j];↵
if(nxt[x]>=idx[p])↵
{↵
nxt[x]=idx[p];↵
mxval[j].push_back(nxt[x]-idx[x]);↵
}↵
else↵
{↵
if(nxt[x]>se[j]) se[j]=nxt[x];↵
val[j].push_back(nxt[x]-idx[x]);↵
}↵
}↵
add[j]=mxadd[j]=0;↵
radixsort(val[j]);↵
getpre(pre[j],val[j]);↵
radixsort(mxval[j]);↵
getpre(mxpre[j],mxval[j]);↵
}↵
for(int ki:ks[i])↵
{↵
tot++;↵
for(j=1;j<=bn;j++)↵
{↵
auto it=lower_bound(val[j].begin(),val[j].end(),ki);↵
ans[tot]+=(val[j].end()-it)*ki;↵
if(it!=val[j].begin()) ans[tot]+=pre[j][it-val[j].begin()-1];↵
it=lower_bound(mxval[j].begin(),mxval[j].end(),ki-mxadd[j]);↵
ans[tot]+=(mxval[j].end()-it)*ki;↵
if(it!=mxval[j].begin()) ans[tot]+=(it-mxval[j].begin())*mxadd[j]+mxpre[j][it-mxval[j].begin()-1];↵
}↵
}↵
}↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(false),cin.tie(0);↵
int T;↵
cin>>T;↵
while(T--)↵
{↵
int i,ki,tot=0;↵
cin>>n;↵
bn=(n-1)/B+1;↵
for(i=1;i<=n;i++) cin>>a[i];↵
for(i=1;i<=n;i++)↵
{↵
cin>>ki;↵
ks[i].resize(ki);↵
for(int &it:ks[i])↵
{↵
cin>>it;↵
ans[++tot]=-(i+it-1);↵
}↵
}↵
vWork();↵
reverse(a+1,a+n+1);↵
for(int x=1;x<=n;x++)↵
t[x]=0;↵
for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();↵
vWork();↵
for(int x=1;x<=n;x++)↵
t[x]=0;↵
for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();↵
for(i=1;i<=tot;i++) cout<<ans[i]<<'\n';↵
tot=0;↵
}↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
