( ext{B - Squares})
解法
先开始觉得要给每一种 (x) 分类… 结果令 (p=x+z,q=x-z)，这样只用保证 (pequiv qpmod 2)，(pqle N) 即可。
( ext{C - LIS to Original Sequence})
解法
没睡午觉，感觉脑子已经不太清醒了… 我一直以为是计算 ( m LIS) 是 (A) 的排列个数。但是我也不会这个排列组合问题。
首先可以想到，在 (A_i) 前放置一个 (>A_i) 的数一定是不优的。对于 (P_1) 只能放置 (A_1)，不然 ( m LIS) 会增加到 (k+1) 项。不过，对于 (A_i,i>1)，都可以在 (A_{i-1},A_i) 之间放置 一个 小于 (A_i) 的数。(A_k) 会有些麻烦，需要将比它大的数逆序放在它之前，比它小的数逆序放在它之后。
代码
#include <cstdio>
#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((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
int n,k,a[maxn];
queue <int> q;
vector <int> ans;
int main() {
n=read(9),k=read(9);
for(int i=1;i<=k;++i)
a[i]=read(9);
for(int i=1;i<a[1];++i)
q.push(i);
for(int i=1;i<k;++i) {
print(a[i],' ');
if(!q.empty()) {
print(q.front(),' ');
q.pop();
}
for(int j=a[i]+1;j<a[i+1];++j)
q.push(j);
}
q.push(a[k]);
for(int i=a[k]+1;i<=n;++i)
q.push(i);
while(!q.empty()) {
ans.push_back(q.front());
q.pop();
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i)
print(ans[i],' ');
puts("");
return 0;
}
( ext{D - Unique Subsequence})
解法
只需要保证对于所选下标 (p_i,p_{i+1})，满足 (jin [p_i,p_{i+1}]) 时，(a_j eq a_{p_i},a_j eq a_{p_{i+1}})。
设 (dp_i) 为以 (i) 为结尾得到的满足条件的字符串个数，它的前缀和可以用树状数组维护。再用 (lst) 维护上一个同种 (a) 的下标。容易发现，只有 (jin[lst_{a_i},i)) 可以进行贡献，而且 (lst_{a_i}) 对应的 (mathtt {dp}) 值应从前缀和中减去，因为它一定会被 (i) 干扰。
代码
#include <cstdio>
#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((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
const int maxn=2e5+5,mod=998244353;
int dp[maxn],n,lst[maxn];
int c[maxn];
int lowbit(int x) {
return x&-x;
}
int inc(int x,int y) {
if(x+y>=mod)
return x+y-mod;
if(x+y<0)
return x+y+mod;
return x+y;
}
void add(int x,int k) {
while(x<=n)
c[x]=inc(c[x],k),
x+=lowbit(x);
}
int ask(int x) {
int r=0;
while(x)
r=inc(r,c[x]),
x-=lowbit(x);
return r;
}
int main() {
n=read(9);
for(int i=1;i<=n;++i) {
int x=read(9);
if(!lst[x]) {
dp[i]=inc(ask(i-1),1);
add(i,dp[i]);
lst[x]=i;
}
else {
dp[i]=inc(ask(i-1),-ask(lst[x]-1));
add(lst[x],-dp[lst[x]]);
lst[x]=i;
add(i,dp[i]);
}
}
print(ask(n),'
');
return 0;
}