NYCU 2024 Team Selection Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105381
比賽影片
---
No
記分板
---
題解
---
### A. Trip Counting I
---
#### 題目摘要
一個$n$點完全圖給你刪掉的邊找三環
#### 想法
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> adj(n);
vector<pii> edge;
rep (i, 0, m) {
int a, b; cin >> a >> b;
a--, b--;
if (a > b) swap(a, b);
edge.pb({a, b});
adj[a].pb(b);
adj[b].pb(a);
}
ll ans = 1LL * n * (n - 1) * (n - 2) / 6;
ans -= 1LL * m * (n - 2);
rep (i, 0, n) {
int sz = adj[i].size();
ans += 1LL * sz * (sz - 1) / 2;
}
vector<vector<int>> big(n);
for (auto [a, b] : edge) {
if (adj[a].size() < adj[b].size()) swap(a, b);
big[a].pb(b);
}
ll cyc = 0;
vector<int> cur(n, -1);
rep (i, 0, n) if (big[i].size()) {
for (int x : adj[i]) cur[x] = i;
for (int sm : big[i]) {
for (int x : adj[sm]) if (x != i) cyc += cur[x] == i;
}
}
ans -= cyc / 3;
cout << ans * 6 << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### B. Trip Counting II
---
#### 題目摘要
找四環
#### 想法
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> adj(n);
vector<int> ord(n), rk(n);
rep (i, 0, m) {
int a, b; cin >> a >> b;
a--, b--;
adj[a].pb(b);
adj[b].pb(a);
}
iota(all(ord), 0);
sort(all(ord), [&](int a, int b) {
return adj[a].size() > adj[b].size();
});
rep (i, 0, n) rk[ord[i]] = i;
vector<vector<int>> D(n);
rep (u, 0, n) {
for (int v : adj[u]) if (rk[u] < rk[v]) {
D[u].pb(v);
}
}
// ord = sort by deg decreasing, rk[ord[i]] = i
// D: undirected to directed edge from rk small to rk big
vector<int> vis(n);
ll c3 = 0, c4 = 0;
for (int x : ord) { // c3
for (int y : D[x]) vis[y] = 1;
for (int y : D[x]) for (int z : D[y]) c3 += vis[z];
for (int y : D[x]) vis[y] = 0;
}
for (int x : ord) { // c4
for (int y : D[x]) for (int z : adj[y])
if (rk[z] > rk[x]) c4 += vis[z]++;
for (int y : D[x]) for (int z : adj[y])
if (rk[z] > rk[x]) --vis[z];
}
cout << c4 * 8 << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### C. Trip Counting III
---
#### 題目摘要
找五環
#### 想法
枚舉所有點當起點，若有一條邊兩端點的距離都是2則它有可能是5環，然而有可能兩點走的路徑有重複邊，將它們扣掉就是答案
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ORENOOSHIKYOUMOKAWAIII ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
const int N=1005;
vector<int> v[N];
pii p[N];
ll dp[3][N][N];
void _solve(){
int n, m;
cin >> n >> m;
for(int i=0;i<m;i++){
cin >> p[i].F >> p[i].S;
v[p[i].F].push_back(p[i].S);
v[p[i].S].push_back(p[i].F);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=0;
dp[0][i][i]=1;
for(int j=1;j<=2;j++){
for(int k=0;k<m;k++){
auto [x, y]=p[k];
dp[j][i][x]+=dp[j-1][i][y];
dp[j][i][y]+=dp[j-1][i][x];
}
}
for(int j=1;j<=n;j++) if (dp[0][i][j]) dp[2][i][j]=0;
}
ll cnt=0;
for(int k=0;k<m;k++){
auto [x, y]=p[k];
if (x==y) continue;
for(int j=1;j<=n;j++){
ll tmp=(dp[2][j][x]-dp[1][j][y])*(dp[2][j][y]-dp[1][j][x]);
tmp=max(0LL, tmp);
cnt+=tmp;
}
for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) if (i!=j){
if (dp[2][j][x]&&dp[2][j][y]&&dp[1][j][i]){
cnt-=dp[1][i][x]*dp[1][i][y];
}
}
}
cnt<<=1;
cout << cnt << '\n';
}
int main(){
ORENOOSHIKYOUMOKAWAIII;
int _t=1;
//cin >> _t;
while(_t--) _solve();
}
```
:::
### D. Rearrangement
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### E. Elimination Game
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### F. Destroying Monsters
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### G. Graph Coloring Problem
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### H. Points Separation
---
#### 題目摘要
#### 想法
建凸包，先判是不是在多邊形外，是的話花 $O(N)$ 把所有點到點跟點到線段的距離取min再/2。
總複雜度$O(NQ)$
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
struct point{
ll x, y;
point operator + (point p1) { return {x + p1.x, y + p1.y}; }
point operator - (point p1) { return {x - p1.x, y - p1.y}; }
ll operator ^ (point p1) { return x * p1.y - p1.x * y; }
ll operator * (point p1) { return x * p1.x + y * p1.y; }
bool operator < (const point &p1) const {
if (x != p1.x) return x < p1.x;
return y < p1.y;
};
};
ostream& operator << (ostream &os, const point &p) { return os << '(' << p.x << "," << p.y << ')'; }
double abs2(point o) { return o * o; }
double abs(point o) { return sqrtl(abs2(o)); }
int sign(ll num){
if (fabs(num) <= eps) return 0;
return num > 0 ? 1 : -1;
}
int ori(point o, point a, point b) {
return sign((a - o) ^ (b - o));
}
bool onseg(point p1, point p2, point p3) { // {online, online, other}
point va = p1 - p3, vb = p2 - p3;
return (va ^ vb) == 0 && (va * vb) <= 0;
}
bool banana(point p1, point p2, point q1, point q2) {
if (onseg(p1, p2, q1) || onseg(p1, p2, q2) ||
onseg(q1, q2, p1) || onseg(q1, q2, p2)) return 1;
if (ori(p1, p2, q1) * ori(p1, p2, q2) < 0 &&
ori(q1, q2, p1) * ori(q1, q2, p2) < 0) return 1;
return 0;
}
double PointSegDist(point q0, point q1, point p) {
if (sign(abs(q0 - q1)) == 0) return abs(q0 - p);
if (sign((q1 - q0) * (p - q0)) >= 0 && sign((q0 - q1) * (p - q1)) >= 0)
return fabs(((q1 - q0) ^ (p - q0)) / abs(q0 - q1));
return min(abs(p - q0), abs(p - q1));
}
bool PointInConvex(const vector<point> &C, point p, bool strict = true) {
// no three points are collinear
int a = 1, b = C.size() - 1, r = !strict;
if (C.size() == 0) return false;
if (C.size() < 3) return r && onseg(C[0], C.back(), p);
if (ori(C[0], C[a], C[b]) > 0) swap(a, b);
if (ori(C[0], C[a], p) >= r || ori(C[0], C[b], p) <= -r) return false;
while (abs(a - b) > 1) {
int c = a + b >> 1;
(ori(C[0], C[c], p) > 0 ? b : a) = c;
}
return ori(C[a], C[b], p) < r;
}
void solve() {
int n, q; cin >> n >> q;
vector<point> pt(n);
for (auto &[x, y] : pt) cin >> x >> y;
// need vector<pll> pt
sort(all(pt));
auto cross = [&](point a, point b) -> ll {
return (a ^ b);
};
vector<point> hull;
rep (i, 0, n) {
while (hull.size() >= 2 && cross(pt[i] - hull.end()[-2], hull.back() - hull.end()[-2]) >= 0) {
hull.pop_back();
}
hull.pb(pt[i]);
}
int sz = hull.size();
for(int i = n - 2; i >= 0; --i){
while(hull.size() > sz && cross(pt[i] - hull.end()[-2], hull.back() - hull.end()[-2]) >= 0) hull.pop_back();
hull.pb(pt[i]);
}
hull.pop_back();
sz = hull.size();
// cout << hull;
cout << fixed << setprecision(15);
while (q--) {
point p; cin >> p.x >> p.y;
if (PointInConvex(hull, p, 0)) {
cout << -1 << '\n';
} else {
double ans = 9e18;
rep (i, 0, sz) {
chmin(ans, abs(p - hull[i]));
chmin(ans, PointSegDist(hull[i], hull[(i + 1) % sz], p));
}
if (sz == 0) ans = abs(p - pt[0]);
ans /= 2;
cout << ans << '\n';
}
}
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### I. LIS Decrement
---
#### 題目摘要
#### 想法
做個$O(N^2)$LIS的DP，考慮建flow模型，先把點拆成入點跟出點中間連權重流量，將dp[i] == 1的點連到源點，dp[i] == lis的點連到匯點，然後中間的邊就看dp的轉移關係建邊，最後答案就是最小割。
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
struct Dinic {
struct edge {
int v, r; ll rc;
};
vector<vector<edge>> adj;
vector<int> dis, it;
Dinic(int n) : adj(n), dis(n), it(n) {}
void add_edge(int u, int v, ll c) {
adj[u].pb({v, adj[v].size(), c});
adj[v].pb({u, adj[u].size() - 1, 0});
}
bool bfs(int s, int t) {
fill(all(dis), IINF);
queue<int> q;
q.push(s);
dis[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& [v, r, rc] : adj[u]) {
if (dis[v] < IINF || rc == 0) continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
return dis[t] < IINF;
}
ll dfs(int u, int t, ll cap) {
if (u == t || cap == 0) return cap;
for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
auto &[v, r, rc] = adj[u][i];
if (dis[v] != dis[u] + 1) continue;
ll tmp = dfs(v, t, min(cap, rc));
if (tmp > 0) {
rc -= tmp;
adj[v][r].rc += tmp;
return tmp;
}
}
return 0;
}
ll flow(int s, int t) {
ll ans = 0, tmp;
while (bfs(s, t)) {
fill(all(it), 0);
while ((tmp = dfs(s, t, IINF)) > 0) {
ans += tmp;
}
}
return ans;
}
bool inScut(int u) { return dis[u] < IINF; }
};
void solve() {
int n; cin >> n;
vector<int> a(n), w(n);
rep (i, 0, n) cin >> a[i];
rep (i, 0, n) cin >> w[i];
Dinic G(2 * n + 2);
int s = 2 * n, t = s + 1;
int lis = 1;
vector<int> dp(n);
dp[0] = 1;
rep (i, 1, n) {
dp[i] = 1;
rep (j, 0, i) if (a[i] > a[j]) chmax(dp[i], dp[j] + 1);
chmax(lis, dp[i]);
}
rep (i, 0, n) {
G.add_edge(i, i + n, w[i]);
if (dp[i] == 1) G.add_edge(s, i, IINF);
if (dp[i] == lis) G.add_edge(i + n, t, IINF);
rep (j, 0, i) if (a[i] > a[j] && dp[i] == dp[j] + 1) G.add_edge(j + n, i, IINF);
}
cout << accumulate(all(w), 0) - G.flow(s, t) << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### J. Randomized String Matching Algorithm
---
#### 題目摘要
拿字串t去匹配每個s的子字串，方法是做k次隨機抽一個位置匹配，求正確匹配的機率。
#### 想法
會發現對於原本就是好的匹配的怎麼抽都是好的，因此題目要求的是$P[每一個匹配不起來的子字串都不被正確匹配]$，若是一個子字串有$m_i$個位置一樣，那麼答案是$\prod \limits _{i = 0} ^{s - t + 1} (1 - (\frac{m_i}{|t|})^k)$。
變成要如何快速求出$m_i$，可以發現這就是字元匹配，因此可以考慮對每個字母$c$拆開來做，將這個位置是不是$c$當成0/1陣列，然後就是很經典的一邊反過來做捲積。
總複雜度$O(8*\text |S|\log \text |S|)$
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder_modint {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename conditional<is_same<T, __int128_t>::value ||
is_same<T, __int128>::value,
true_type,
false_type>::type;
template <class T>
using is_unsigned_int128 =
typename conditional<is_same<T, __uint128_t>::value ||
is_same<T, unsigned __int128>::value,
true_type,
false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename conditional<is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
true_type,
false_type>::type;
template <class T>
using is_signed_int = typename conditional<(is_integral<T>::value &&
is_signed<T>::value) ||
is_signed_int128<T>::value,
true_type,
false_type>::type;
template <class T>
using is_unsigned_int =
typename conditional<(is_integral<T>::value &&
is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
true_type,
false_type>::type;
template <class T>
using to_unsigned = typename conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename conditional<is_signed<T>::value,
make_unsigned<T>,
common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename is_integral<T>;
template <class T>
using is_signed_int =
typename conditional<is_integral<T>::value && is_signed<T>::value,
true_type,
false_type>::type;
template <class T>
using is_unsigned_int =
typename conditional<is_integral<T>::value &&
is_unsigned<T>::value,
true_type,
false_type>::type;
template <class T>
using to_unsigned = typename conditional<is_signed_int<T>::value,
make_unsigned<T>,
common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
// @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;
}
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 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};
}
// 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`
explicit 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;
}
};
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = is_base_of<modint_base, T>;
template <class T> using is_modint_t = enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public true_type {};
template <class T>
using is_dynamic_modint_t = enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder_modint
// need atcoder_modint
namespace atcoder_convolution {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// 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 (atcoder_modint::internal::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);
template <class mint,
int g = internal::primitive_root<mint::mod()>,
atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
array<mint, rank2 + 1> root; // root[i]^(2^i) == 1
array<mint, rank2 + 1> iroot; // root[i] * iroot[i] == 1
array<mint, max(0, rank2 - 2 + 1)> rate2;
array<mint, max(0, rank2 - 2 + 1)> irate2;
array<mint, max(0, rank2 - 3 + 1)> rate3;
array<mint, max(0, rank2 - 3 + 1)> irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
}
{
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
}
};
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly(vector<mint>& a) {
int n = int(a.size());
int h = internal::ceil_pow2(n);
static const fft_info<mint> info;
int len = 0; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
for (int s = 0; s < (1 << len); s++) {
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
if (s + 1 != (1 << len))
rot *= info.rate2[bsf(~(unsigned int)(s))];
}
len++;
} else {
// 4-base
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i + offset].val();
auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
auto a1na3imag =
1ULL * mint(a1 + mod2 - a3).val() * imag.val();
auto na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
if (s + 1 != (1 << len))
rot *= info.rate3[bsf(~(unsigned int)(s))];
}
len += 2;
}
}
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(vector<mint>& a) {
int n = int(a.size());
int h = internal::ceil_pow2(n);
static const fft_info<mint> info;
int len = h; // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
for (int s = 0; s < (1 << (len - 1)); s++) {
int offset = s << (h - len + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
irot.val();
;
}
if (s + 1 != (1 << (len - 1)))
irot *= info.irate2[bsf(~(unsigned int)(s))];
}
len--;
} else {
// 4-base
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
auto a0 = 1ULL * a[i + offset + 0 * p].val();
auto a1 = 1ULL * a[i + offset + 1 * p].val();
auto a2 = 1ULL * a[i + offset + 2 * p].val();
auto a3 = 1ULL * a[i + offset + 3 * p].val();
auto a2na3iimag =
1ULL *
mint((mint::mod() + a2 - a3) * iimag.val()).val();
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] =
(a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
a[i + offset + 2 * p] =
(a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
irot2.val();
a[i + offset + 3 * p] =
(a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
irot3.val();
}
if (s + 1 != (1 << (len - 2)))
irot *= info.irate3[bsf(~(unsigned int)(s))];
}
len -= 2;
}
}
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_naive(const vector<mint>& a,
const vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
vector<mint> ans(n + m - 1);
if (n < m) {
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
ans[i + j] += a[i] * b[j];
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
}
return ans;
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_fft(vector<mint> a, vector<mint> b) {
int n = int(a.size()), m = int(b.size());
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
} // namespace internal
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(vector<mint>&& a, vector<mint>&& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(const vector<mint>& a,
const vector<mint>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
return internal::convolution_fft(a, b);
}
template <unsigned int mod = 998244353,
class T,
enable_if_t<atcoder_modint::internal::is_integral<T>::value>* = nullptr>
vector<T> convolution(const vector<T>& a, const vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = atcoder_modint::static_modint<mod>;
vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(move(a2), move(b2));
vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
vector<long long> convolution_ll(const vector<long long>& a,
const vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
atcoder_modint::internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
atcoder_modint::internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
atcoder_modint::internal::inv_gcd(MOD1 * MOD2, MOD3).second;
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
// B = 2^63, -B <= x, r(real value) < B
// (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
// r = c1[i] (mod MOD1)
// focus on MOD1
// r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
// r = x,
// x - M' + (0 or 2B),
// x - 2M' + (0, 2B or 4B),
// x - 3M' + (0, 2B, 4B or 6B) (without mod!)
// (r - x) = 0, (0)
// - M' + (0 or 2B), (1)
// -2M' + (0 or 2B or 4B), (2)
// -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
// we checked that
// ((1) mod MOD1) mod 5 = 2
// ((2) mod MOD1) mod 5 = 3
// ((3) mod MOD1) mod 5 = 4
long long diff =
c1[i] - atcoder_modint::internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder_convolution
using mint = atcoder_modint::modint998244353;
using namespace atcoder_convolution;
ostream& operator << (ostream &os, const mint &p) { os << p.val(); return os; }
void solve() {
string s, t; cin >> s >> t;
int k; cin >> k;
reverse(all(t));
int n = s.size(), m = t.size();
vector<mint> cnt(n + m - 1, 0);
rep (ch, 0, 8) {
vector<mint> a(n, 0), b(m, 0);
rep (i, 0, n) if (s[i] - 'a' == ch) a[i] = 1;
rep (i, 0, m) if (t[i] - 'a' == ch) b[i] = 1;
auto c = convolution(a, b);
rep (i, 0, n + m - 1) cnt[i] += c[i];
}
// rep (i, m - 1, n + m - 2) cout << cnt[i] << ' ';
mint ans = 1, inv = mint(m).inv();
rep (i, m - 1, m - 1 + n - m + 1) if (cnt[i] != m) {
ans *= 1 - (cnt[i] * inv).pow(k);
}
cout << ans << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### K. King's Challenge
---
#### 題目摘要
求$\frac{n!}{(n-k)!}$去掉後綴0的後5位數
#### 想法
$設\text {fact}(n)=n!去掉後綴0後\bmod 10^5，F(n)=\prod_{i=1, i\not\mid 2, i\not\mid 5}^{n}i$，則能寫出遞迴式$\text {fact}(n)=\frac{\text {fact}(\lfloor\frac{n}{2}\rfloor)\times \text {fact}(\lfloor\frac{n}{5}\rfloor)}{\text {fact}(\lfloor\frac{n}{10}\rfloor)}\times 2^{\lfloor\frac{n}{2}\rfloor-\lfloor\frac{n}{5}\rfloor}\times F(n)$
首先，先處理$F(n)$，而$F(n)$有循環節，所以可以先預處理完。
再來看$\text {fact}(n)$，最棘手的就是除法，若$\text {fact}(n)$不是2或5的倍數，就能用歐拉定理解決，因此在處理$\text {fact}(n)$時不要把二的冪次方乘進去，而是計算冪次方個數並最後再來處理。
最後，求出來的是$\bmod 10^5$的答案，但答案是能有前綴0的，所以只要在$k$夠小時暴力做就好
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long loli;
typedef pair<int, int> pii;
typedef pair<loli, loli> pll;
#define F first
#define S second
const loli mod=100000, phi=40000;
loli f[100005];
map<loli, pll> dp;
loli fpow(loli x, loli k){
loli res=1;
while(k){
if (k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
pll solve(loli n){
if (dp.find(n)!=dp.end()) return dp[n];
loli cnt2=n/2, cnt5=n/5, cnt10=n/10;
auto [res2, two2]=solve(n/2);
auto [res5, two5]=solve(n/5);
auto [res10, two10]=solve(n/10);
loli res=res2*res5%mod*fpow(res10, phi-1)%mod;
res=res*f[n%mod]%mod;
loli two=two2+two5-two10+(cnt2-cnt5);
return dp[n]={res, two};
}
void _solve(){
loli n, k;
scanf("%lld%lld", &n, &k);
if (k<=100){
loli tmp=1;
loli cnt2=0, cnt5=0;
for(loli i=n-k+1;i<=n;i++){
loli t=i;
while(t%10==0) t/=10;
while(t%2==0) cnt2++, t/=2;
while(t%5==0) cnt5++, t/=5;
tmp*=t;
if (tmp>mod) break;
}
if (tmp<mod){
if (cnt2>cnt5){
cnt2-=cnt5;
if (cnt2<=16){
tmp<<=cnt2;
if (tmp<mod){
printf("%lld\n", tmp);
return;
}
}
}else{
cnt5-=cnt2;
if (cnt5<=7){
for(int i=0;i<cnt5;i++) tmp*=5LL;
if (tmp<mod){
printf("%lld\n", tmp);
return;
}
}
}
}
}
pll x=solve(n);
pll y=solve(n-k);
loli ans=x.F*fpow(y.F, phi-1)%mod;
ans=ans*fpow(2LL, x.S-y.S)%mod;
int d=0;
int p=1;
while(p<=ans) d++, p*=10;
for(int i=0;i<5-d;i++) printf("0");
printf("%lld\n", ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int _t=1;
scanf("%d", &_t);
f[0]=1;
for(loli i=1;i<=100000;i++){
f[i]=f[i-1];
if ((i%2==0)||(i%5==0)) continue;
f[i]*=i;
f[i]%=mod;
}
dp[0]={1, 0};
while(_t--) _solve();
}
```
:::
### L. The Bag of Forgotten Coins
---
#### 題目大綱
#### 想法
:::spoiler 實作
```cpp=
```
:::
### M. The Tale of Professor Alya and the H-Index
---
#### 題目大綱
#### 想法
:::spoiler 實作
```cpp=
```
:::
Sign in with Wallet
Connect another wallet