[Contest on 2022.5.13] 再这样熬夜我就要猝死了([contest on May 13, 2022] if I stay up late like this, I will die suddenly)

\(\cal T_1\) 出题人

\(\mathbb{D}\rm escription\)

毒瘤出题人接到了一次出题任务,共需要提供 \(n\) 道题,其中第 \(i\) 道题要求难度为 \(10^{a_i}\),保证 \(a_i\) 互不相同。

毒瘤出题人的常见手段,就是把两种想法拼接起来,出成一道题。我们定义,一道拼接题的难度,是其两个想法难度的乘积。两道题可以共用同一个想法,一个想法也可以和自己拼接起来出成题。

现在出题人确定了 \(n\) 种想法,第 \(i\) 种想法的难度为 \(10^{b_i}\),他提供的每道题目都由其中恰好两个想法拼凑而成。想法的难度不必互不相同。

你通过小道消息知道了 \(n\) 和 \(\{a\}\),请你求出一种可能的出题方案;当然,有的小道消息根本就是假新闻,那么你也要声明不可能存在出题方案。

\(n\le 30,|a_i|\le 2\cdot 10^9\),需要注意的是,最终构造出的 \(b_i\) 应满足 \(|b_i|\le 10^{10}\).

\(\mathbb{S}\rm olution\)

不妨先手玩一下 \(n\le 3\) 的情况:在玩 \(n=2\) 的时候可以发现,我们必须保证存在一个偶数(不妨令其为 \(a_1\)),这样就可以令 \(b=\{a_1/2,a_2-a_1/2\}\) 从而构造出解。可以发现这种方案是可拓展的,如果 \(\{a\}\) 中出现了偶数,我们都可以用这种方法 \(\mathcal O(n)\) 地构造出解,所以接下来我们只需要解决 \(\{a\}\) 中全为奇数的情况。

然后问题就变得困难,我就不会做了。事实上可以这样思考:为啥问题不好做了呢?可以想到,如果是 \(n+1\) 个想法拼出 \(n\) 道题,我们可以容易地利用差分值构造答案。也就是说,如果将一道题看作连接两个想法的一条边,一条链的情况是非常好做的,难搞的是环。对于此题,由于是 \(n\) 个点 \(n\) 条边,会且仅会生成一个环,只要解决这个环的构造就解决了这道题。

不妨令这个环节点权值依次为 \(b_1,b_2,\dots,b_k\),那么 \(a_i=b_i+b_{i+1}(b_{k+1}=b_1)\),那么 \(\sum a_i=2\cdot \sum b_i\),由于 \(a_i\) 均为奇数,那么 \(k\) 一定是偶数。同时还可以得出 \(\sum b_i=a_1+a_3+\dots +a_{k-1}=a_2+a_4+\dots +a_k\)。显然这两个条件都是构造出环的必要条件,现在我们证明这同时也是充分条件:令 \(b_1=0\),同时令 \(a_i=b_i+b_{i+1}\),显然我们能使 \(a_1,a_2,\dots,a_{k-1}\) 均满足条件,现在就是证明 \(a_k=b_k+b_1\),这其实也很简单,因为奇数项和偶数项和相同,且我们已经得到了 \(a_2,a_4,\dots,a_{k-2}\) 的 \(\{b\}\) 表达,相减即可得 \(a_k=b_k+b_1\).

所以问题变成了:找到两个大小相同且元素互异的 \(a\) 集合,使得两个集合的和相等。

可以想到直接枚举 \(\mathcal O(3^n)\),显然不能通过;更进一步可以使用 \(\mathtt{dp}\),但是直接 \(\mathtt{dp}\) 元素个数似乎不太好搞,我们不妨将这个限制放到元素和相同这个限制里(其实本质空间都是一样的):取 \(M=1+\sum a_i\),令 \(a’_i=a_i+M\)。设 \(dp(i,j)\) 为确定前 \(i\) 个元素的归属,选定两个集合相差为 \(j\) 的解,复杂度 \(\mathcal O(n^2\cdot \sum a_i)\).

事实上,这不是折半搜索的经典问题吗?复杂度 \(\mathcal O(3^{n/2})\),因为写得很粗糙,所以还写了个哈希表卡常。

哦对了,如果 \(b\) 算出来不满足条件,再 \(\text{shuffle}\) 一下应该也没啥问题。

$\mathbb{C}\rm ode $

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template <class T>
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp]=x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

# include <ctime>
# include <random>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <int,int> par;

const int maxn = 35;
const ll infty = 1e10;

int n,cnt;
ll a[maxn],b[maxn],sm[1<<15];

struct Edge { int nxt,fir,sec; ll val; } e[(int)2e7];
struct hash_table {
	const static int key = 1e7;
	int head[key],hash_cnt;
	inline void ins(const ll& val,int Fir,int Sec) {
		e[++hash_cnt].nxt=head[val%key], head[val%key]=hash_cnt;
		e[hash_cnt].fir=Fir, e[hash_cnt].sec=Sec, e[hash_cnt].val=val;
	}
	inline par _find(const ll& val) {
		for(int i=head[val%key]; i; i=e[i].nxt)
			if(val==e[i].val) return make_pair(e[i].fir,e[i].sec);
		return make_pair(-1,-1);
	}
} mp[31];

inline void even_solver(int pose) {
	puts("Yes");
	for(int i=1;i<=n;++i)
		if(i==pose) print(a[i]/2,' ');
		else print(a[i]-a[pose]/2,' ');
	for(int i=1;i<=n;++i)
		if(i==pose) printf("%d %d\n",i,i);
		else printf("%d %d\n",pose,i);
}
inline void add(const ll& val) { ++cnt, b[cnt]=val-b[cnt-1]; }
inline void odd_solver(int S,int T) {
	static bool cho[40],ban; ban=true;
	static mt19937 SEED(time(0));
	static int s[20],t[20],ls,lt,p[40],ref[40]; ls=lt=0;
	memset(cho+1,0,sizeof(bool)*(n+1));
	for(int i=1;i<=n;++i) if(S>>i-1&1) 
		s[++ls]=i, cho[i] = true;
	for(int i=1;i<=n;++i) if(T>>i-1&1) 
		t[++lt]=i, cho[i] = true;
	while(ban) {
		for(int i=1;i<=ls;++i) p[i]=i;
		shuffle(p+1,p+ls+1,SEED); cnt=1;
		for(int i=1;i<ls;++i)
			add(a[s[p[i]]]), add(a[t[p[i]]]),
			ref[s[p[i]]]=(i<<1)-1, ref[t[p[i]]]=(i<<1);
		add(a[s[p[ls]]]); ref[s[p[ls]]]=(ls<<1)-1;
		ban = false;
		for(int i=2;i<=(ls<<1);++i)
			if(b[i]>infty || b[i]<-infty) { ban=true; break; }
	}
	puts("Yes");
	for(int i=1;i<=(ls<<1);++i) print(b[i],' ');
	for(int i=1;i<=n;++i) if(!cho[i]) print(a[i],' '); puts("");
	for(int i=1;i<=n;++i)
		if(cho[i]) {
			if(t[p[ls]]==i) printf("%d %d\n",1,ls<<1);
			else printf("%d %d\n",ref[i],ref[i]+1);
		} else printf("%d %d\n",1,++cnt);
}

int main() {
	freopen("problemsetter.in","r",stdin);
	freopen("problemsetter.out","w",stdout);
	n=read(9); int pose=0; par _end=make_pair(-1,-1),it;
	for(int i=1;i<=n;++i) {
		a[i]=read(9);
		if(a[i]%2==0) pose=i;
	}
	if(pose) return even_solver(pose), (0-0);
	int m = n>>1, S = 1<<m, T = 1<<n-m;
	for(int s=1;s<S;++s) {
		sm[s] = sm[s&s-1]+a[__builtin_ffs(s&-s)];
		for(int t=s;t;--t&=s) {
			ll dv = sm[t]-sm[s^t];
			int dc = __builtin_popcount(t)-__builtin_popcount(s^t);
			if(!dv && !dc) return odd_solver(t,s^t), (0-0);
			if(dv>=0 && dc>=0 && mp[dc]._find(dv)==_end)
				mp[dc].ins(dv,t,s^t);
		}
	} 
	for(int s=1;s<T;++s) {
		sm[s] = sm[s&s-1]+a[__builtin_ffs(s&-s)+m];
		for(int t=s;t;--t&=s) {
			ll dv = sm[t]-sm[s^t];
			int dc = __builtin_popcount(t)-__builtin_popcount(s^t);
			if(!dv && !dc) return odd_solver(t<<m,(s^t)<<m), (0-0);
			if(dv>=0 && dc>=0 && (it=mp[dc]._find(dv))!=_end)
				return odd_solver((t<<m)^it.second,((s^t)<<m)^it.first), (0-0);
		}
	}
	puts("No");
	return 0;
}

\(\cal T_2\) 彩色挂饰

\(\mathbb{D}\rm escription\)

\(\mathbb{S}\rm olution\)

圆方树,这个真的完全不会,等学会了再回来填坑。

“这个人也许永远不回来填坑了,也许明天回来填坑。”

“这个人也许永远不回来填坑了,也许明天回来填坑。”

$\mathbb{C}\rm ode $

\(\cal T_3\) 逆转函数

\(\mathbb{D}\rm escription\)

考虑一个值域为 \([1,m]\) 的正整数序列 \(\{v_1,v_2,\dots,v_k\}\),令 \(A=\{1,2,\dots,m\}\),对于一个函数 \(f:A\rightarrow A\),我们认为它是合法的当且仅当:序列 \(\{f(v_1),f(v_2),\dots,f(v_k)\}\) 和序列 \(\{v_k,v_{k-1},\dots,v_1\}\) 相同。

给定值域为 \([1,m]\) 的正整数序列 \(\{a\}\),你要对它的所有子区间求出对应的合法函数的个数,并输出这些个数的和对 \(998244353\) 取模的值。

\(n,m\le 3\cdot 10^5\).

\(\mathbb{S}\rm olution\)

\(\text{Subtask 1}\):\(n\le 5000\)

可以固定子区间的中点向外拓展,预处理 \(\text{pre},\text{nxt}\) 表示元素的前驱与后继就可以 \(\mathcal O(1)\) 拓展。时间复杂度 \(\mathcal O(n^2)\)。同时,我们定义 “逆转区间” 为:至少存在一个逆转函数,使得其作用在此区间上合法;再定义 “区间权值” 为:区间内已被固定的函数值个数。

\(\text{Subtask 2}\):\(m=2\)

可以发现,个全 \(1\) 或者全 \(2\) 区间有 \(2\) 个逆转函数;对于个同时含 \(1,2\) 的区间,如果它是回文串,或者它翻转后将 \(1,2\) 对换与原串相同,则逆转函数数量为 \(1\)。

这似乎不太好统计,全 \(1\) 或者全 \(2\) 区间是包括在回文串之中的,而 “翻转后将 \(1,2\) 对换与原串相同” 的情况则是与前几种情况毫无交集的。所以我们可以将全 \(1\) 或者全 \(2\) 区间都计数一次,将回文串也都计数一次,对于最后一种情况,我们发现这实际上是改变一下判断条件的回文串,也都计数一次。用 \(\rm manacher\) 硬跑就行了。

\(\text{Subtask 3}\):\(\text{In all cases}\)

大家猜猜我倍增数组写反过多少次?___,__!

一件非常神奇的事情是,逆转区间实际上和回文串十分类似(我觉得出题人设置的部分分还是很有启发性的,虽然我没想出来 qwq)!为啥捏?这是因为如果有一个大的逆转区间,现在有一个小逆转区间被完全包含,那么这个小逆转区间对称位置的区间一定也是逆转区间。证明就是考虑最基础的一对关系 \(f(a)=b,f(b)=a\),列出各个变量之间的关系即可,这里就不再赘述。

既然这样,我们就可以用一个类 \(\rm manacher\) 的算法来求解这个问题,本质上也就是优化我们的暴力。显然我们不能再使用 \(p_i = \min\{p_{2\cdot \text{mid}-i}, \text{R} – i\}\) 这样简单递推了,这是因为我们还要递推区间权值,就必须定位是从哪个区间继承而来。所以还需要存储一个前驱,然后倍增跳父亲。

复杂度证明就是 \(\rm manacher\) 的复杂度证明,因为 \(\rm R\) 范围是 \(\mathcal O(n)\) 的,所以均摊复杂度 \(\mathcal O(n\log n)\).

$\mathbb{C}\rm ode $

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template <class T>
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp]=x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

const int maxn = 6e5+5;
const int mod = 998244353;

inline void inc(int& x,int y) { x=(x+y>=mod?x+y-mod:x+y); }

int f[20][maxn],idx,ref[maxn];
int n,m,a[maxn],all,ans,pw[maxn];
int pre[maxn],nxt[maxn],head[maxn];
struct node { int tms,val,len; } t[maxn];

inline bool ok(int l,int r) {
	if(!(l>0 && r<=all)) return false;
	if(!a[l] || !a[r]) return a[l]==a[r];
	if(nxt[l]>=r && pre[r]<=l) return true;
	if(nxt[l]>=r || pre[r]<=l) return false;
	return l+r==pre[r]+nxt[l];
}

int main() {
	freopen("invfunc.in","r",stdin);
	freopen("invfunc.out","w",stdout);
	n=read(9), m=read(9); ++all;
	for(int i=1;i<=n;++i)
		a[++all]=read(9), ++all;
	for(int i=pw[0]=1; i<=all; ++i)
		pre[i] = head[a[i]],
		nxt[pre[i]] = head[a[i]] = i,
		pw[i] = 1ll*pw[i-1]*m%mod;
	for(int i=1;i<=all;++i) 
		if(!nxt[i]) nxt[i]=all+1;
	t[idx=1].len=ref[1]=1;
	for(int i=2,mid=1; i<=all; ++i) {
		if(mid+t[ref[mid]].len<=i)
			t[ref[i]=++idx].len=1, t[idx].val=(i&1^1);
		else {
			ref[i] = ref[(mid<<1)-i];
			for(int j=19;~j;--j)
				if(mid+t[ref[mid]].len<=i+t[f[j][ref[i]]].len)
					ref[i] = f[j][ref[i]];
		}
		if(mid+t[ref[mid]].len<=i+t[ref[i]].len) {
			int now = ref[i]; mid=i;
			while(ok(i-t[now].len,i+t[now].len)) { 
				f[0][now=++idx]=ref[i], t[now] = t[ref[i]], t[now].tms=0;
				if(a[i-t[now].len] && nxt[i-t[now].len]>=i+t[now].len) ++t[now].val;
				if(a[i+t[now].len] && pre[i+t[now].len]<i-t[now].len) ++t[now].val;
				++ t[now].len, ref[i]=now;
				for(int j=1;j<=19;++j) f[j][now] = f[j-1][f[j-1][now]];
			}
		}
		++ t[f[0][ref[i]]].tms; // 将贡献累计在边界不为空的区间
	}
	for(int i=idx;i;--i)
		t[f[1][i]].tms += t[i].tms, // 跳过边界为空的不合法区间
		inc(ans,1ll*pw[m-t[i].val]*t[i].tms%mod);
	print(ans,'\n');
	return 0;	
}
————————

\(\ cal t_1 \) author

\(\mathbb{D}\rm escription\)

The author of the cancer problem received a problem-solving task, and a total of \ (n \) problems need to be provided. Among them, the difficulty of the \ (I \) problem is \ (10 ^ {a_i} \), so as to ensure that \ (a_i \) are different from each other.

The common method of cancer problem setters is to splice the two ideas into one problem. We define that the difficulty of a puzzle is the product of the difficulty of its two ideas. Two questions can share the same idea, and one idea can also be spliced with yourself to form a problem.

Now the author has determined \ (n \) ideas. The difficulty of the \ (I \) idea is \ (10 ^ {b_i} \), and each question he provides is made up of exactly two ideas. The difficulty of ideas need not be different from each other.

You know \ (n \) and \ (\ {a \} \) through the grapevine. Please find out a possible solution; Of course, some grapevine news is false news at all, so you should also state that there can be no problem solution.

\(n \ Le 30, | a | I | \ le 2 \ cdot 10 ^ 9 \), it should be noted that the final \ (B | I \) should meet \ (| B | I | \ Le 10 ^ {10} \)

\(\mathbb{S}\rm olution\)

You might as well play \ (n \ le 3 \) first: when playing \ (n = 2 \), you can find that we must ensure that there is an even number (you might as well make it \ (a_1 \)), so that you can make \ (b = \ {a_1 / 2, a_2-a_1 / 2 \} \) to construct the solution. It can be found that this scheme is extensible. If even numbers appear in \ (\ {a \} \), we can use this method \ (\ mathcal o (n) \) to construct the solution, so next we only need to solve the case where all numbers in \ (\ {a \} \) are odd.

Then the problem becomes difficult and I won’t do it. In fact, we can think like this: why is it difficult to do it? It is conceivable that if it is \ (n + 1 \) ideas to spell out \ (n \) questions, we can easily use the difference value to construct the answer. In other words, if a problem is regarded as an edge connecting two ideas, the situation of a chain is very easy to do, and the difficult thing is the ring. For this problem, because it is \ (n \) points \ (n \) edges, only one ring will be generated. As long as we solve the construction of this ring, we can solve this problem.

Let the weights of this link point be \ (b_1, b_2, \ dots, b_k \), then \ (a_i = b_i + b_ {I + 1} (b_ {K + 1} = b_1) \), then \ (\ sum a_i = 2 \ cdot \ sum b_i \), because \ (a_i \) are odd, then \ (K \) must be even. At the same time, we can also get \ (\ sum b_i = a_1 + a_3 + \ dots + a_ {k-1} = a_2 + a_4 + \ dots + a_k \). Obviously, these two conditions are necessary conditions for constructing a ring. Now we prove that they are also sufficient conditions: let \ (b_1 = 0 \) and let \ (a_i = b_i + b_{I + 1} \), obviously we can make \ (a_1, a_2, \ dots, a_ {k-1} \) meet the conditions. Now we prove that \ (a_k = b_k + b_1 \), which is actually very simple, because the odd and even terms are the same, and we have obtained the \ (\ {B \} \) expression of \ (a_2, a_4, \ dots, a_ {K-2} \), Subtract to get \ (a_k = b_k + b_1 \)

So the problem becomes: find two sets of \ (a \) with the same size and different elements, so that the sum of the two sets is equal.

It is conceivable to directly enumerate \ (\ mathcal o (3 ^ n) \), which obviously cannot be passed; Further, you can use \ (\ mathtt {DP} \), but the number of direct \ (\ mathtt {DP} \) elements doesn’t seem easy. We might as well put this limit in the same element and the same limit (in fact, the essential space is the same): take \ (M = 1 + \ sum a_i \) and make \ (a ‘_i = a_i + m \). Set \ (DP (I, J) \) as the attribution of the first \ (I \) elements, and select the solution whose difference between the two sets is \ (J \), with complexity \ (\ mathcal o (n ^ 2 \ cdot \ sum a_i) \)

In fact, isn’t this the classic problem of half search? Complexity \ (\ mathcal o (3 ^ {n / 2}) \), because the writing is very rough, a hash table is also written.

Oh, by the way, if the calculation of \ (B \) does not meet the conditions, it should be no problem to \ (\ text {shuffle} \) again.

$\mathbb{C}\rm ode $

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template <class T>
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp]=x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

# include <ctime>
# include <random>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <int,int> par;

const int maxn = 35;
const ll infty = 1e10;

int n,cnt;
ll a[maxn],b[maxn],sm[1<<15];

struct Edge { int nxt,fir,sec; ll val; } e[(int)2e7];
struct hash_table {
	const static int key = 1e7;
	int head[key],hash_cnt;
	inline void ins(const ll& val,int Fir,int Sec) {
		e[++hash_cnt].nxt=head[val%key], head[val%key]=hash_cnt;
		e[hash_cnt].fir=Fir, e[hash_cnt].sec=Sec, e[hash_cnt].val=val;
	}
	inline par _find(const ll& val) {
		for(int i=head[val%key]; i; i=e[i].nxt)
			if(val==e[i].val) return make_pair(e[i].fir,e[i].sec);
		return make_pair(-1,-1);
	}
} mp[31];

inline void even_solver(int pose) {
	puts("Yes");
	for(int i=1;i<=n;++i)
		if(i==pose) print(a[i]/2,' ');
		else print(a[i]-a[pose]/2,' ');
	for(int i=1;i<=n;++i)
		if(i==pose) printf("%d %d\n",i,i);
		else printf("%d %d\n",pose,i);
}
inline void add(const ll& val) { ++cnt, b[cnt]=val-b[cnt-1]; }
inline void odd_solver(int S,int T) {
	static bool cho[40],ban; ban=true;
	static mt19937 SEED(time(0));
	static int s[20],t[20],ls,lt,p[40],ref[40]; ls=lt=0;
	memset(cho+1,0,sizeof(bool)*(n+1));
	for(int i=1;i<=n;++i) if(S>>i-1&1) 
		s[++ls]=i, cho[i] = true;
	for(int i=1;i<=n;++i) if(T>>i-1&1) 
		t[++lt]=i, cho[i] = true;
	while(ban) {
		for(int i=1;i<=ls;++i) p[i]=i;
		shuffle(p+1,p+ls+1,SEED); cnt=1;
		for(int i=1;i<ls;++i)
			add(a[s[p[i]]]), add(a[t[p[i]]]),
			ref[s[p[i]]]=(i<<1)-1, ref[t[p[i]]]=(i<<1);
		add(a[s[p[ls]]]); ref[s[p[ls]]]=(ls<<1)-1;
		ban = false;
		for(int i=2;i<=(ls<<1);++i)
			if(b[i]>infty || b[i]<-infty) { ban=true; break; }
	}
	puts("Yes");
	for(int i=1;i<=(ls<<1);++i) print(b[i],' ');
	for(int i=1;i<=n;++i) if(!cho[i]) print(a[i],' '); puts("");
	for(int i=1;i<=n;++i)
		if(cho[i]) {
			if(t[p[ls]]==i) printf("%d %d\n",1,ls<<1);
			else printf("%d %d\n",ref[i],ref[i]+1);
		} else printf("%d %d\n",1,++cnt);
}

int main() {
	freopen("problemsetter.in","r",stdin);
	freopen("problemsetter.out","w",stdout);
	n=read(9); int pose=0; par _end=make_pair(-1,-1),it;
	for(int i=1;i<=n;++i) {
		a[i]=read(9);
		if(a[i]%2==0) pose=i;
	}
	if(pose) return even_solver(pose), (0-0);
	int m = n>>1, S = 1<<m, T = 1<<n-m;
	for(int s=1;s<S;++s) {
		sm[s] = sm[s&s-1]+a[__builtin_ffs(s&-s)];
		for(int t=s;t;--t&=s) {
			ll dv = sm[t]-sm[s^t];
			int dc = __builtin_popcount(t)-__builtin_popcount(s^t);
			if(!dv && !dc) return odd_solver(t,s^t), (0-0);
			if(dv>=0 && dc>=0 && mp[dc]._find(dv)==_end)
				mp[dc].ins(dv,t,s^t);
		}
	} 
	for(int s=1;s<T;++s) {
		sm[s] = sm[s&s-1]+a[__builtin_ffs(s&-s)+m];
		for(int t=s;t;--t&=s) {
			ll dv = sm[t]-sm[s^t];
			int dc = __builtin_popcount(t)-__builtin_popcount(s^t);
			if(!dv && !dc) return odd_solver(t<<m,(s^t)<<m), (0-0);
			if(dv>=0 && dc>=0 && (it=mp[dc]._find(dv))!=_end)
				return odd_solver((t<<m)^it.second,((s^t)<<m)^it.first), (0-0);
		}
	}
	puts("No");
	return 0;
}

\(\ cal t_2 \) color Pendant

\(\mathbb{D}\rm escription\)

\(\mathbb{S}\rm olution\)

Round square tree, this is really not at all. Come back to fill the pit when you learn it.

“This person may never come back to fill the pit, and may come back tomorrow to fill the pit.”

“This person may never come back to fill the pit, and may come back tomorrow to fill the pit.”

$\mathbb{C}\rm ode $

\(\ cal t_3 \) reversal function

\(\mathbb{D}\rm escription\)

Consider a positive integer sequence \ (\ {v_1, v_2, \ dots, v_k \} \) with a value range of \ ([1, M] \), so that \ (a = \ {1,2, \ dots, m \} \) is legal for a function \ (F: a \ rightarrow a \), if and only if the sequence \ (\ {f (v_1), f (v_2), \ dots, f (v_k) \} \) is the same as the sequence \ (\ {v_k, v_k-1}, \ dots, v_1 \} \).

Given a positive integer sequence \ (\ {a \} \) with a value range of \ ([1, M] \), you need to find the number of corresponding legal functions for all its sub intervals, and output the sum of these numbers and the modular value of \ (998244353 \).

\(n,m\le 3\cdot 10^5\).

\(\mathbb{S}\rm olution\)

\(\text{Subtask 1}\):\(n\le 5000\)

The midpoint of the fixed subinterval can be extended outward. The preprocessing \ (\ text {pre}, \ text {NXT} \) represents the precursor and successor of the element, which can be extended \ (\ mathcal o (1) \). Time complexity \ (\ mathcal o (n ^ 2) \). At the same time, we define the “reversal interval” as: there is at least one reversal function, making its action legal in this interval; Then define “interval weight” as: the number of fixed function values in the interval.

\(\text{Subtask 2}\):\(m=2\)

It can be found that there are \ (2 \) reversal functions in a full \ (1 \) or full \ (2 \) interval; For an interval containing \ (1,2 \) at the same time, if it is a palindrome string, or if it reverses the \ (1,2 \) exchange with the original string, the number of reversal functions is \ (1 \).

It seems that it is not easy to make statistics. The full \ (1 \) or full \ (2 \) interval is included in the palindrome string, while the case of “reversing \ (1,2 \) to be the same as the original string” has no intersection with the previous cases. Therefore, we can count all \ (1 \) or all \ (2 \) intervals once and palindrome strings once. For the last case, we find that this is actually counting palindrome strings that change the judgment conditions once. Just run hard with \ (\ RM manacher \).

\(\text{Subtask 3}\):\(\text{In all cases}\)

Guess how many times I’ve written the multiplication array upside down? __, _!

A very magical thing is that the reversal interval is actually very similar to the palindrome string (I think the partial score set by the questioner is still very enlightening, although I didn’t think of it qwq)! Why pinch? This is because if there is a large reversal interval and now a small reversal interval is completely included, the interval at the symmetrical position of the small reversal interval must also be a reversal interval. The proof is to consider the most basic pair of relations \ (f (a) = B, f (b) = a \), and list the relations between various variables, which will not be repeated here.

In this case, we can use an algorithm like \ (\ RM manacher \) to solve this problem, which is essentially to optimize our violence. Obviously, we can’t use such simple recursion as \ (p_i = \ min \ {p_ {2 \ cdot \ text {mid}-i}, \ text {r} – I \} \) anymore. This is because we have to recurs the interval weight, so we must locate which interval we inherit from. Therefore, you also need to store a precursor, and then double jump father.

The complexity proof is the complexity proof of \ (\ RM manacher \). Since the range of \ (\ RM R \) is \ (\ mathcal o (n) \), the complexity \ (\ mathcal o (n \ log n) \) is shared equally

$\mathbb{C}\rm ode $

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template <class T>
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp]=x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

const int maxn = 6e5+5;
const int mod = 998244353;

inline void inc(int& x,int y) { x=(x+y>=mod?x+y-mod:x+y); }

int f[20][maxn],idx,ref[maxn];
int n,m,a[maxn],all,ans,pw[maxn];
int pre[maxn],nxt[maxn],head[maxn];
struct node { int tms,val,len; } t[maxn];

inline bool ok(int l,int r) {
	if(!(l>0 && r<=all)) return false;
	if(!a[l] || !a[r]) return a[l]==a[r];
	if(nxt[l]>=r && pre[r]<=l) return true;
	if(nxt[l]>=r || pre[r]<=l) return false;
	return l+r==pre[r]+nxt[l];
}

int main() {
	freopen("invfunc.in","r",stdin);
	freopen("invfunc.out","w",stdout);
	n=read(9), m=read(9); ++all;
	for(int i=1;i<=n;++i)
		a[++all]=read(9), ++all;
	for(int i=pw[0]=1; i<=all; ++i)
		pre[i] = head[a[i]],
		nxt[pre[i]] = head[a[i]] = i,
		pw[i] = 1ll*pw[i-1]*m%mod;
	for(int i=1;i<=all;++i) 
		if(!nxt[i]) nxt[i]=all+1;
	t[idx=1].len=ref[1]=1;
	for(int i=2,mid=1; i<=all; ++i) {
		if(mid+t[ref[mid]].len<=i)
			t[ref[i]=++idx].len=1, t[idx].val=(i&1^1);
		else {
			ref[i] = ref[(mid<<1)-i];
			for(int j=19;~j;--j)
				if(mid+t[ref[mid]].len<=i+t[f[j][ref[i]]].len)
					ref[i] = f[j][ref[i]];
		}
		if(mid+t[ref[mid]].len<=i+t[ref[i]].len) {
			int now = ref[i]; mid=i;
			while(ok(i-t[now].len,i+t[now].len)) { 
				f[0][now=++idx]=ref[i], t[now] = t[ref[i]], t[now].tms=0;
				if(a[i-t[now].len] && nxt[i-t[now].len]>=i+t[now].len) ++t[now].val;
				if(a[i+t[now].len] && pre[i+t[now].len]<i-t[now].len) ++t[now].val;
				++ t[now].len, ref[i]=now;
				for(int j=1;j<=19;++j) f[j][now] = f[j-1][f[j-1][now]];
			}
		}
		++ t[f[0][ref[i]]].tms; // 将贡献累计在边界不为空的区间
	}
	for(int i=idx;i;--i)
		t[f[1][i]].tms += t[i].tms, // 跳过边界为空的不合法区间
		inc(ans,1ll*pw[m-t[i].val]*t[i].tms%mod);
	print(ans,'\n');
	return 0;	
}