构造一个 n3n^3 个点的无向图 GG,方法如下:

  1. 给定 33nn 个点的无向图 G1,G2,G3G_1,G_2,G_3
  2. 构造 n3n^3 个点,标号是一个三元组 <i,j,k>\left<i,j,k\right>
  3. 对于 G1G_1 中的边 <u,v>\left<u,v\right>,连边 <u,j,k>\left<u,j,k\right><v,j,k>\left<v,j,k\right>
  4. 对于 G2G_2 中的边 <u,v>\left<u,v\right>,连边 <i,u,k>\left<i,u,k\right><i,v,k>\left<i,v,k\right>
  5. 对于 G3G_3 中的边 <u,v>\left<u,v\right>,连边 <i,j,u>\left<i,j,u\right><i,j,v>\left<i,j,v\right>
  6. 对于 GG 上的一个点 <i,j,k>\left<i,j,k\right>,其点权为 1018(i+j+k){10}^{18(i+j+k)}

现在,要你求出 GG 的最大独立集大小膜 998244353998244353 以后的值。

2n105,1m1,m2,m31052\le n\le 10^5,1\le m_1,m_2,m_3\le 10^5

给出一种生成长度为 3n3n 的排列 PP 的方法:

  1. 先生成一个长度为 3n3n 的排列 AA,然后对于 k[0,n1]\forall k\in [0,n-1],将 3n+1,3n+2,3n+33n + 1, 3n + 2, 3n + 3 分成一块。
  2. nn 个指针,开始指向这 nn 个块的开头。
  3. 每次选择这 nn 个指针指向的数中最小的并将其放在 PP 的末尾,将这个指针向后移一位,如果移出块了,将指针删除。
  4. 回到 2 操作直到所有指针均被删除。

现在要你求出,这样的方式共能生成多少种本质不同的排列 AA,答案对 mm 取模。

1n2×103,108m109+71\le n\le 2\times 10^3,10^8\le m\le 10^9+7

nn 条线 mm 个平衡器,从左往右第 ii 个平衡器连接了 xi,yix_i,y_i 条电线(1xi<yin1\le x_i<y_i\le n),每个平衡器都有一个状态:向上或向下。考虑一个令牌,从最左边的某一条导线开始,如果在第 ii 个位置,如果他在 xix_i 导线上且平衡器状态向下,那么就到 yiy_i,同理如果在 yiy_i 且状态向上,则到 xix_i。记 kik_i 表示令牌从导线 ii 开始到无穷远处是他在哪条导线上。

让你构造两种解,每种解用一个字符串表示,表示每个平衡器的状态。第一组解要求所有的 kik_i 相等,第二组接要求至少有两个 kik_i 不相等。无解输出 1-1

数据范围 2n5×104,1m1052\le n\le 5\times 10^4,\,1\le m\le 10^5

问存在多少个长度为 n(2n5000)n\,(2\le n\le 5000) 的单调不减序列 aa,满足 1ain1\le a_i\le n,且对于任意 k(1k<n)k\,(1\le k<n),都有:对任意大小为 kk 的子集 SS 和大小为 k+1k+1 的子集 TT,满足 xSAx<xTAx\sum_{x\in S}A_x<\sum_{x\in T}A_x。答案对大质数 mm 取模。

有一段标号从 -\infty++\infty 的序列 AA,初始是 Ai=0A_i=0。现在有一个人在 00 位置,有一段操作序列 ss,依次进行操作。

假设 ii 时刻这个人在位置 pp,如果 sis_i'+',则将 ApA_p11,如果是 '-',则减 11;如果是 '<' 则该人左移一格,否则是 '>' 则右移一格。

要求数出 ss 的所有连续子串中最终得到的 AAss 最终得到相同 AA 序列的个数。

数据范围 s250000|s|\le 250000