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

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

### $$\mathbb{D}\rm escription$$

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

### $\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;
inline void ins(const ll& val,int Fir,int Sec) {
e[hash_cnt].fir=Fir, e[hash_cnt].sec=Sec, e[hash_cnt].val=val;
}
inline par _find(const ll& val) {
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)
ref[s[p[i]]]=(i<<1)-1, ref[t[p[i]]]=(i<<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);
for(int i=1;i<=n;++i) {
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;
}


### $$\mathbb{S}\rm olution$$

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

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

### $$\mathbb{D}\rm escription$$

$$n,m\le 3\cdot 10^5$$.

### $\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];
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);
for(int i=1;i<=n;++i)
for(int i=pw[0]=1; i<=all; ++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;
}

————————

### $$\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;
inline void ins(const ll& val,int Fir,int Sec) {
e[hash_cnt].fir=Fir, e[hash_cnt].sec=Sec, e[hash_cnt].val=val;
}
inline par _find(const ll& val) {
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)
ref[s[p[i]]]=(i<<1)-1, ref[t[p[i]]]=(i<<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);
for(int i=1;i<=n;++i) {
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;
}


### $$\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{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$$.

### $$\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];
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);
for(int i=1;i<=n;++i)
for(int i=pw[0]=1; i<=all; ++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;
}