苏州做网站优化,万能浏览器官方免费版,互联网广告优势,网站托管维护合同文章目录 前言时间安排及成绩题解A. 江桥不会做的签到题#xff08;简单dp#xff09;B. 江桥树上逃#xff08;堆#xff0c;模拟#xff09;C. 括号平衡路径#xff08;点分治#xff09;D. 回到起始顺序#xff08;dp#xff0c;组合数学#xff09; 前言
T2好难… 文章目录 前言时间安排及成绩题解A. 江桥不会做的签到题简单dpB. 江桥树上逃堆模拟C. 括号平衡路径点分治D. 回到起始顺序dp组合数学 前言
T2好难T4好难。T3写的好粪T1好水。。
时间安排及成绩
7:40 开题。看题目说明好像有很签到的题7:40 - 7:45 T1看完了为啥感觉有点难难道是容斥但是数据规模也不可能啊。旁边有人叫T1真的水。就我秒不掉吗7:45 - 8:05 秉着T1就是签到题的想法继续想T1。发现不用关心具体填什么数只需保证相对关系逆序对数就不会变。所以直接暴力dp好像就做完了。写完一边过了所有样例。8:05 - 8:10 看T2woc这T2啥东西啊。看着像贪心又好像模拟。但是这数据规模为啥这么逆天而且每个点都有牛好像不好搞。8:10 - 8:50 又想了40minT2还是只会20pts暴力。特殊性质都不知道该咋写。只好先放弃了。8:50 - 8:55 T3题看懂了就是树上每个节点都有一个括号求树上一条路径使括号匹配合法并且嵌套数最大。 n n n 的范围为啥是 5 × 1 0 4 5 \times 10^4 5×104。难道要上根号或者 l o g log log 特别多8:55 - 9:30 太饿了好像没啥劲思考。感觉只会 n 2 n^2 n2 的暴力。特殊性质最开始以为是菊花后来发现还有可能是链或者蒲公英。那写起来就太粪了啊。。。9:30 - 10:10 吃了个面包然后嫌教室太吵了出去想。想到了可以点分治。然后考虑怎样合并两条链。显然需要维护倒着看和正着看两种链还要维护前缀最大值最小值啥的。然后好像就可以单 l o g log log 那这数据范围一度以为自己假了后来想想感觉没啥问题。就回去写了。10:10 - 11:10 写了好长时间中间忘了点分治的板子了还回去重新看了看。然后写的很丑但是感觉思路很清晰。写完自信测样例。卧槽怎么都输出 0 0 0 啊。打表发现我分治的根从第二次开始就都是 0 0 0好逆天。11: 10 - 1130 终于看出了是我的变量重名了。改完之后每次分治的根不是 0 0 0 了但是输出还是不对。后来发现每次合并是左边链不能从根开始。改完之后怎么还不对推一下样例发现从子树到根的路径算错了。然后特殊处理了一下这样的路径就把样例都过了。11:30 - 11:45 线上评测一下。woc全部MLE了。但是数组只开到了 5 e 4 5e4 5e4 啊怎么会MLE后来尝试把代码注释一部分一点一点找把哪里加上就会MLE。最后发现 void 函数打成了 int没有返回值。然后就寄了11:45 - 11:53 火速把T2暴力写了一开始还一直错。后来发现没开long long。11:53 - 12:00 尝试写T4 20分但是由于题目看不懂失败了。。
估分100 20 100 0 220 分数100 20 100 0 220 rk6
点评为没挂分。。
题解
A. 江桥不会做的签到题简单dp 分析
签到题。
设 d p i , j dp_{i, j} dpi,j 表示前 i i i 个位置填 1 ∼ i 1 \sim i 1∼i形成了 j j j 个逆序对的方案数。注意这里的 1 ∼ i 1 \sim i 1∼i 可以理解为 具有相对大小的 i i i 个数字。
然后转移可以枚举第 i i i 位填的是 相对顺序中第几的数字 d p i , j ∑ k m a x ( 0 , j − i 1 ) j d p i − 1 , k dp_{i, j} \sum_{kmax(0, j - i 1)}^{j} dp_{i - 1, k} dpi,j∑kmax(0,j−i1)jdpi−1,k
前缀和随便优化一下。每个限制就是保留一个状态的方案数其他状态赋值为 0 0 0。
CODE
#includebits/stdc.h
using namespace std;
const int N 5010;
typedef long long LL;
const LL mod 1e9 7;
LL f[N][N], S[N]; // f[i][j] 表示前i个逆序对数为j的方案数
int n, m;
struct limit {int p, c;
}l[N];
bool cmp(limit x, limit y) {return x.p y.p;
}
int main() {scanf(%d%d, n, m);for(int i 1; i m; i ) {scanf(%d%d, l[i].p, l[i].c);}sort(l 1, l m 1, cmp);int k 1;f[0][0] 1LL; for(int i 1; i n; i ) {for(int j 0; j 5000; j ) {if(j 0) S[j] f[i - 1][j];else S[j] (S[j - 1] f[i - 1][j]) % mod;}for(int j 0; j 5000; j ) {f[i][j] ((S[j] - (j - (i - 1) 0 ? S[j - (i - 1) - 1] : 0LL)) % mod mod) % mod;}if(k m i l[k].p) {for(int j 0; j 5000; j ) {if(j ! l[k].c) f[i][j] 0;}k ;}}printf(%lld\n, f[n][l[m].c]); return 0;
}B. 江桥树上逃堆模拟
原题链接 分析
感觉这题好难。。。
直接说正解
首先有一个贪心的性质如果一个点内还有人并且它的父边流量还没满那么把这条边流满肯定更优。也就是说一条边能够流满我们就让它流满。
然后我们假设当前是所有边都流满的状态设为 G 0 G_0 G0。那么这样的状态会在某个时刻发生改变这是由于 某个点 x x x 的流入量小于流出量那么会在每秒流出时消耗它自己点内的人直到点内的人都流走。这时这个点的父边就没办法流满了这个点相当于变成了一个 中继站由儿子流入的量会直接从父边流出并且父边流不满。那么 x x x 就是无用的我们考虑这时 将 x x x 和它的父亲合并成一个点。
也就是说边的流量集 G G G 会发生变化由 G 0 G_0 G0 变为 G 1 G_1 G1然后再由 G 1 G_1 G1 变成 G 2 G_2 G2 等。这样的变化是由于一个点内原来的人全部净流出去的结果所以这样的变化应当不超过 n n n 次。或者由于每次变化后我们都把两个点合成一个点因此合并次数不会超过 n n n 次。
那么我们考虑按照 时间顺序 维护这样的变化。对于一个点记一个 p a s s i pass_i passi 表示 i i i 号点当前的 净流出量。那么 p a s s i pass_i passi 的计算方式就是父边的流量减去儿子边的流量和。如果当前 i i i 号点的人数为 c i c_i ci那么前 ⌊ c i p a s s i ⌋ \left \lfloor \frac{c_i}{pass_i} \right \rfloor ⌊passici⌋ 时刻显然 i i i 号点都 有能力让父边满流。如果超出了这个时间就可以把 i i i 和 f a i fa_i fai 合成一个点。合并关系可以用 并查集 维护。
我们考虑把二元组 ( i (i (i ⌊ c i p a s s i ⌋ ) \left \lfloor \frac{c_i}{pass_i} \right \rfloor) ⌊passici⌋) 插入堆中堆里把 ⌊ c i p a s s i ⌋ \left \lfloor \frac{c_i}{pass_i} \right \rfloor ⌊passici⌋ 小的放在堆顶。然后把询问按照时间顺序由小到大排序用一个指针维护处理到哪一个询问了。
拿出栈顶二元组如果当前询问时间小于等于栈顶时间那么这个询问的答案就是 c 1 − p a s s 1 × t i c_1 - pass_1 \times t_i c1−pass1×ti。 t i t_i ti 表示询问的时间。减号是由于 p a s s i pass_i passi 等于 流出量减去流入量那么 − p a s s 1 -pass_1 −pass1 就表示流入量。如果当前询问时间大于栈顶时间那么我们需要检验栈顶的节点 x x x 是否已经合并过即 F i n d ( i ) Find(i) Find(i) 是否等于 i i i。如果合并过那么这个状态不能用否则需要把 i i i 合并到 F i n d ( f a i ) Find(fa_i) Find(fai) 的点集中。记 F i n d ( f a i ) Find(fa_i) Find(fai) 为 F a Fa Fa合并方法是让 p a s s F a pass_{Fa} passFa 加上 p a s s i pass_i passi让 c F a c_{Fa} cFa 加上 c i c_i ci。( p a s s F a pass_{Fa} passFa 中减去了 i i i 到父亲的流量 p a s s i pass_{i} passi 中加上了 i i i 到父亲的流量正负抵消)。这个合并可以理解为 这个时刻之后 可以把 初始状态 看作 x x x 和它的父亲缩成了一个点它们两个之间的边不用管这个点初始的人的数量就是 c i c F a c_i c_{Fa} cicFa。然后这个点的 净流量 就是 p a s s x p a s s F a pass_x pass_{Fa} passxpassFa。然后这个点能保持父边满流的时间就是 ⌊ c x c F a p a s s x p a s s F a ⌋ \left \lfloor \frac{c_x c_{Fa}}{pass_{x} pass_{Fa}} \right \rfloor ⌊passxpassFacxcFa⌋。这样在上面算答案时 c 1 − p a s s 1 × t i c_1 - pass_1 \times t_i c1−pass1×ti 就可以对应成 点 1 1 1 初始人数为 c 1 c_1 c1保持净流入量是 − p a s s 1 -pass_1 −pass1持续了 t t t 时刻 后点内的人数。
时间复杂度 O ( n × l o g 2 n ) O(n \times log_2n) O(n×log2n)。 代码不长。 CODE
// 首先有一个贪心能满流就让满流这样一定不劣
// 考虑如果t时间内都是以 flow 的流量流入那么t时间后这个点的人数就是 t * flow
// 但是一条边不可能一直满流边的流量情况会出现变化这个变化是由于某个点里的人为了让它的父边满流因此是负收入在某一个时刻原来这个点里的人消耗完了
// 那么开一个堆维护这些变化时刻。如果一个点原来的人走完了那么它实际上就是一个中继点可以直接把它和它的父亲合并
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
typedef long long LL;
int n, qc, fa[N], bin[N];
LL c[N], m[N], pass[N], ans[N], sum;
struct node {LL tim; int x;friend bool operator (node a, node b) {return a.tim b.tim;}
};
priority_queue node q;
struct Q {int t, idx;
}qq[N];
bool cmp(Q a, Q b) {return a.t b.t;
}
int Find(int x) {return x bin[x] ? x : bin[x] Find(bin[x]);}
int main() {scanf(%d%d, n, qc);for(int i 2; i n; i ) {scanf(%d%lld%lld, fa[i], c[i], m[i]);pass[i] m[i], pass[fa[i]] - m[i];sum c[i];}for(int i 1; i n; i ) bin[i] i;for(int i 1; i qc; i ) {scanf(%d, qq[i].t);qq[i].idx i;}for(int i 1; i n; i ) {if(pass[i] 0) q.push((node) {c[i] / pass[i], i});}sort(qq 1, qq qc 1, cmp);int p 1;while(!q.empty() p qc) {node Tp q.top(); q.pop();LL tim Tp.tim; int x Tp.x;while(p qc qq[p].t tim) {ans[qq[p].idx] c[1] - pass[1] * (1LL * qq[p].t);p ;}if(Find(x) ! x) continue; //刚才被合并过了那么这个状态不能用 // 可以合并 int Fa Find(fa[x]); // 找到父亲所在的那个节点 pass[Fa] pass[x]; c[Fa] c[x]; bin[x] Fa;if(pass[Fa] 0) q.push((node) {c[Fa] / pass[Fa], Fa});}for(int i p; i qc; i ) {ans[qq[i].idx] sum; // 合成1个点了 }for(int i 1; i qc; i ) printf(%lld\n, ans[i]); return 0;
}总结这类 把节点合并 来 简化状态 或者 减少决策 的思路还要多学习。
C. 括号平衡路径点分治
原题链接 分析
感觉遇到这种 求所有路径中最优值 的题都可以往点分治上想。
对于当前根考虑如何在 O ( 子树大小 ) O(子树大小) O(子树大小) 的复杂度内求出所有 经过根 的路径的最优值。
还是按照点分治的套路我们考虑 把两条在不同子树的路径 合起来。我们把左括号看作 1 1 1右括号看作 − 1 -1 −1。同时对于一个点 x x x 到当前根 r t rt rt维护这条路径 从 x x x 往 r t rt rt 看 的前缀最小值 m n 1 [ x ] mn_1[x] mn1[x]前缀最大值 m x 1 [ x ] mx_1[x] mx1[x] 以及 从 r t rt rt 往 x x x看 的前缀最小值 m n 2 [ x ] mn_2[x] mn2[x]前缀最大值 m x 2 [ x ] mx_2[x] mx2[x]。还需要维护 x x x 到 r t rt rt 的路径和 s x s_x sx。那么两条路径 x → r t x \to rt x→rt r t → y rt \to y rt→y 能够合并需要满足以下条件 s x s y 0 s_x s_y 0 sxsy0 m n 1 [ x ] ≥ 0 mn_1[x] \geq 0 mn1[x]≥0 且 s x m n 2 [ y ] ≥ 0 s_x mn_2[y] \geq 0 sxmn2[y]≥0
如果满足答案合并后的路径对答案的贡献就是 m a x ( m x 1 [ x ] , s x m x 2 [ y ] ) max(mx_1[x], s_x mx_2[y]) max(mx1[x],sxmx2[y])。
可以维护一个桶 v a l val val v a l i val_i vali 表示已经加入的路劲中 s x i s_x i sxi 且满足 m n 1 [ x ] mn_1[x] mn1[x] 的最大的 m x 1 [ x ] mx_1[x] mx1[x]。然后对一条路径 r t → y rt \to y rt→y 找最优值就是查询 v a l − s y val_{-s_y} val−sy。
注意
由于后加入的路径与前面的路径合并时只能作为后半段但是实际上它还可以作为前半段因此需要 正着做一遍倒着做一遍。由于两条路径合并时不能都含根节点因此可以让加入的路径含根节点查询的路径不含根节点。这是一个边界的细节。
复杂度 O ( n × l o g 2 n ) O(n \times log_2n) O(n×log2n)
CODE
#includebits/stdc.h
#define pb push_back
using namespace std;
const int N 5e4 10;
const int INF 2e6;
int n, fa, a[N], ans, res, root;
int val[N * 2]; // val[i n]维护的是 sum val[i n] 的链mx的最大值
int mx1[N], mx2[N], mn1[N], mn2[N], s[N]; // 分别表示倒着看的最大值正着看的最大值倒着看的最小值正着看的最小值和
bool vis[N];
int sz[N], all, Maxn[N];
char ch[N];
vector int E[N];
void getrt(int x, int fa) {sz[x] 1; Maxn[x] 0;for(auto v : E[x]) {if(v fa || vis[v]) continue;getrt(v, x);Maxn[x] max(Maxn[x], sz[v]);sz[x] sz[v];}Maxn[x] max(Maxn[x], all - sz[x]);if(Maxn[x] Maxn[root]) root x;
}
void getsz(int x, int fa) {sz[x] 1;for(auto v : E[x]) {if(v fa || vis[v]) continue;getsz(v, x);sz[x] sz[v];}
}
void add(int x) { // 加入 x 作为 倒着 if(mn1[x] 0) { // 大于0才加入 val[s[x] n] max(val[s[x] n], mx1[x]);}
}
void del(int x) { // 删去 x 作为 倒着 val[s[x] n] -INF;
}
void ask(int x) { // x 为正 if(val[n - s[x]] 0 (-s[x] mn2[x] 0)) { // 存在 res max(res, max(val[n - s[x]], -s[x] mx2[x]));}
}
void calc(int x, int fa) { // x子树里作为正着 if(x fa) {s[x] mx2[x] mn2[x] a[x];}else { s[x] s[fa] a[x];mx2[x] max(mx2[fa], s[x]);mn2[x] min(mn2[fa], s[x]);}ask(x);for(auto v : E[x]) {if(v fa || vis[v]) continue;calc(v, x);}
}
void ins(int x, int fa) { // 插入x子树作为倒着 s[x] s[fa] a[x];mx1[x] max(mx1[fa] a[x], a[x]);mn1[x] min(mn1[fa] a[x], a[x]);if(s[x] 0 mn1[x] 0) res max(res, mx1[x]);add(x);for(auto v : E[x]) {if(v fa || vis[v]) continue;ins(v, x);}
}
void Clear(int x, int fa) {del(x);for(auto v : E[x]) {if(v fa || vis[v]) continue;Clear(v, x);}
}
void query(int x, int fa) {s[x] s[fa] a[x];mx2[x] max(mx2[fa], s[x]);mn2[x] min(mn2[fa], s[x]);if(s[x] 0 mn2[x] 0) res max(res, mx2[x]);for(auto v : E[x]) {if(v fa || vis[v]) continue;query(v, x);}
}
void sol(int rt) { // 以 rt 为根 1是倒着 2是正着 拿正着和倒着匹配 vis[rt] 1;mx1[rt] mn1[rt] s[rt] a[rt];mx2[rt] mn2[rt] a[rt];add(rt); // 加入根 for(int i 0; i E[rt].size(); i ) {int v E[rt][i];if(vis[v]) continue;calc(v, v); // 解决v子树里的答案 ins(v, rt); // 加入 }for(int i 0; i E[rt].size(); i ) { int v E[rt][i];if(vis[v]) continue;Clear(v, rt); // 把它们的答案删去 }del(rt);for(int i E[rt].size() - 1; i 0; i -- ) { // 倒着做一边 int v E[rt][i];if(vis[v]) continue;calc(v, v);ins(v, rt);}for(auto v : E[rt]) {if(vis[v]) continue;query(v, rt); // 光处理根 }for(int i 0; i E[rt].size(); i ) {int v E[rt][i];if(vis[v]) continue;Clear(v, rt);}for(auto v : E[rt]) {if(vis[v]) continue;root 0; all sz[v];getrt(v, rt);getsz(root, 0);sol(root);}
}
void solve2() {all n; root 0; Maxn[0] INF;getrt(1, 0);getsz(root, 0);sol(root);printf(%d\n, res);
}
int main() {for(int i 0; i N * 2; i ) val[i] -INF;scanf(%d, n);for(int i 2; i n; i ) {scanf(%d, fa);E[i].pb(fa); E[fa].pb(i);}for(int i 1; i n; i ) {scanf(\n%c, ch[i]);if(ch[i] () a[i] 1;else a[i] -1;} solve2();return 0;
}D. 回到起始顺序dp组合数学
原题链接 分析
感觉是有很多trick结合的题。
实际上是问你所有 n ! n! n! 个 1 ∼ n 1 \sim n 1∼n 的排列的权值的 乘积。一个排列的权值和计算方式把 i i i 往 a i a_i ai 连一条有向边所有点的出度为 1 1 1入度为 1 1 1形成了若干置换环。这个排列的权值就是 所有环大小的 l c m lcm lcm。
分析
由于 l c m lcm lcm 可能比较大因此直接求某种 l c m lcm lcm 对应的排列数不现实。我们考虑 每种质因数 的贡献。
设 f x f_x fx 表示 l c m lcm lcm 是 x x x 的倍数的排列数。那么答案就是 ∏ p c ≤ n p f p c \prod_{p^c \leq n} p^{f_{p^c}} ∏pc≤npfpc p p p 为质数
考虑一个排列的 l c m lcm lcm 如果包含 p c p^c pc那么这一部分贡献将会在 p f p p^{f_{p}} pfp p f p 2 p^{f_{p^2}} pfp2,…, p f p c p^{f_{p^c}} pfpc 分别被计算一次。那么总共会被计算 c c c贡献不会少。 p c ≤ n p^c \leq n pc≤n 是因为一个 l c m lcm lcm 中包含某个质因数 p p p 的幂一定小于等于 n n n任何一个环的长度都小于等于 n n n因此环长质因数分解后 p p p 的幂肯定小于等于 n n n。那么 l c m lcm lcm 中包含 p p p 的幂一定也小于等于 n n n。
考虑怎样求 f x f_x fx。我们发现如果 x x x 是某个质数的幂那么还有一个好处满足 l c m lcm lcm 是 x x x 的倍数的排列一定至少存在一个置换环的长度是 x x x 的倍数。这个性质很好想 l c m lcm lcm 是每个环长质因数分解后每种质因数取幂次最大的那个。那么一定存在一个环长的质因数的幂次大于等于 x x x 的幂次。这个环长就是 x x x 的倍数。
我们考虑枚举 x x x然后 d p dp dp 设 f i f_i fi 表示长度为 i i i 的排列满足所有置换环的长度都是 x x x 的倍数的排列数。 g i g_i gi 表示长度为 i i i 的排列没有一个置换环 的长度是 x x x 的倍数的方案数。
那么有转移 f i ∑ j ≤ i , x ∣ j C i − 1 j − 1 × f i − j × ( j − 1 ) ! f_i \sum_{j \leq i,x|j}C_{i - 1}^{j - 1} \times f_{i - j} \times (j - 1)! fi∑j≤i,x∣jCi−1j−1×fi−j×(j−1)! g i i ! − ∑ j ≤ i , x ∣ j C i j × f j × g i − j g_i i! - \sum_{j \leq i,x | j}C_{i}^{j} \times f_{j} \times g_{i - j} gii!−∑j≤i,x∣jCij×fj×gi−j
最后 n ! − g n n! - g_n n!−gn 就是 l c m lcm lcm 是 x x x 的倍数的排列数。 f i f_i fi 的转移可以理解为枚举 1 1 1 号位置所在的置换环大小 j j j然后这个置换环的其它位置需要在 i − 1 i - 1 i−1 个位置里面选 j − 1 j - 1 j−1 个还要乘一个圆排列 ( j − 1 ) ! (j - 1)! (j−1)! 表示这个环内的顺序。剩下 i − j i - j i−j 个位置要接着划分为若干个大小是 x x x 的倍数的置换环。 g i g_i gi 的转移是一个容斥总的排列数减去存在某些环的长度是 x x x 的倍数的排列数。枚举这些长度是 x x x 的倍数的置换环的总长度 j j j这一部分的方案是 f j f_j fj然后剩下 i − j i - j i−j 个位置需要划分成长度都不是 x x x 的倍数的环方案是 g i − j g_{i - j} gi−j最后还要乘上 C i j C_{i}^{j} Cij 表示在 i i i 个位置里选 j j j 个位置去构建长度是 x x x 的倍数的置换环。
还要注意一下由于求出的排列数要作为指数去算答案因此它的计算过程中模数应该为 m o d − 1 mod - 1 mod−1。这个数不一定是质数因此需要避免逆元。上面的过程中组合数可以预处理求。
然后直接暴力 dp 复杂度是 O ( n 2 × l o g 2 n ) O(n^2 \times log_2n) O(n2×log2n) 的 枚举 x x x 是 n n n枚举排列的长度 i i i 加上转移是 ∑ i 1 n i x ≤ n × n x \sum_{i 1}^{n} \frac{i}{x} \leq n \times \frac{n}{x} ∑i1nxi≤n×xn。那么总复杂度是 ∑ x 1 n n × n x n × ∑ x 1 n n x n 2 × l o g 2 n \sum_{x 1}^{n} n\times \frac{n}{x} n \times \sum_{x 1}^{n} \frac{n}{x} n^2 \times log_2n ∑x1nn×xnn×∑x1nxnn2×log2n。
但是根据转移方程式我们发现 f i f_i fi 的转移中只有 i ≡ 0 ( m o d x ) i \equiv 0(mod \ x) i≡0(mod x) 的状态有用 g i g_i gi 的转移中只有 i ≡ n ( m o d x ) i \equiv n(mod \ x) i≡n(mod x) 的状态有用。因此不用全部转移只需要转移 n x \frac{n}{x} xn 个状态。每个状态转移 n x \frac{n}{x} xn 次。
复杂度就是 ∑ x 1 n n x × n x ∑ x 1 n n 2 x 2 ≈ n 2 \sum_{x 1}^{n} \frac{n}{x} \times \frac{n}{x} \sum_{x 1}^{n} \frac{n^2}{x^2} \approx n^2 ∑x1nxn×xn∑x1nx2n2≈n2。
这个约等于可以让电脑打表输出一下发现确实不会超过两倍。
CODE
#includebits/stdc.h
using namespace std;
const int N 7550;
typedef long long LL;
bool vis[N];
int n;
LL m1, m2, c[N][N], f[N], g[N]; // f[i], g[i] 分别表示长度为i的置换所有环的长度都是x的倍数所有环的长度都不是x的倍数的排列数
LL res 1LL, fac[N];
inline LL Pow(LL x, LL y, LL mod) {LL res 1LL, k x % mod;while(y) {if(y 1) res (res * k) % mod;y 1;k (k * k) % mod;}return res;
}
int main() {cin n m1;m2 m1 - 1;for(int i 0; i N; i ) for(int j 0; j i; j ) {if(!j) c[i][j] 1LL;else c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % m2;}fac[0] 1LL;for(int i 1; i N; i ) fac[i] fac[i - 1] * (1LL * i) % m2;for(int i 2; i n; i ) {if(!vis[i]) {for(int j i; j * i n; j ) {vis[i * j] 1;}}}for(int i 2; i n; i ) {if(vis[i]) continue;else { // 质数 int x i; LL p 1LL * i, cnt 0; while(x n) { // 计算答案 g[0] f[0] 1LL;for(int j 1; j n; j ) {g[j] f[j] 0;if(j % x 0 % x) { // 转移 f for(int k x; k j; k x) f[j] (f[j] f[j - k] * c[j - 1][k - 1] % m2 * fac[k - 1] % m2) % m2;}if(j % x n % x) { // 转移 g g[j] fac[j];for(int k x; k j; k x) g[j] ((g[j] - g[j - k] * f[k] % m2 * c[j][k] % m2) % m2 m2) % m2;}}cnt (cnt ((fac[n] - g[n]) % m2 m2) % m2) % m2;x x * p;}res (res * Pow(p, cnt, m1)) % m1;}}printf(%lld\n, res);return 0;
}
