把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1698E Permutation Force II
题目大意：存在两个permutation(2e5)a,b和一个s，以及一种操作，这种操作进行n次，第i次可以交换范围在[i,i+s]内的任何两个数字的位置，要将a通过操作变成b，b并不是一个完整的数组，而是有很多-1，可以替换为任何数（需要使结果的b是一个permutation），求b的可能性的数量。

解：

由于操作具有顺序性，实际上可以发现，要将a中一个大的数换掉使得其成为b中对应位置上偏小的数，你只能在这个小数或者其之前去交换他，无论如何，这都要求s>=a[i]-b[i]。
也就是说可能性的b实际上要求每个对位的数都得>=a在这个位置上的数-s。
于是我们得到了一个具有范围限制的全排列问题，由于序列的特性，其实这个全排列非常简单。
首先，原来b里固定的数是没法用的，所以先通过一个前缀和的方式来求出对于每个x，有多少个>=x的数可以用。可以发现这里存在：如果x0<x1，当一个位置上的要求是b[i]>=x1时，我用掉一个数，那么下次到b[j]>=x0的要求时，可用的数就少了一个。从这里可以判断出，我们需要先从较大的x来算起，然后再算小的x，于是将b中对应-1的a从大到小排序起来，通过刚刚的前缀和求出可能性的数量，并使剩下的可能性数量全部-1，答案就是所有可能性的乘积。
题目偏思维，定了个2300个人觉得有点偏高吧。虽然自己也是比赛的时候没做出来之后看了hint做出来了。题目涉及到一个没什么普遍意义的交换结论以及一个有意义的限制全排列做法，还是很不错的。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define PI 3.14159265358979
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll getpos(int p, ll n) {
	return n / cpow(10, p - 1) % 10;
}
ll getwei(ll n) {
	int res = 0;
	while (n) {
		res++;
		n /= 10;
	}
	return res;
}
/*

---------------------------------------------------------------------

*/
ll a[maxn],b[maxn],vis[maxn],chs[maxn];
vector<int> fre;
bool cmp(int i1, int i2) {
	return i1 > i2;
}
int main() {
	cfast;
	int t = 1;
	cin >> t;
	while (t--) {
		fre.clear();
		int n;
		cin >> n;
		int s;
		cin >> s;
		inc(i, 0, n) {
			vis[i + 1] = 0;
			cin >> a[i];
		}
		int f = 0;
		inc(i, 0, n) {
			cin >> b[i];
			vis[b[i]] = 1;
			if (b[i]>0&&b[i] < a[i] - s) {
				f = 1;
			}
		}
		if (f == 1) {
			cout << 0 << endl;
			continue;
		}
		inc(i, 0, n) {
			if (b[i] == -1)fre.push_back(a[i]);
		}
		ll ans = 1;
		chs[n + 1] = 0;
		for (int i = n; i >= 1; i--) {
			chs[i] = chs[i + 1] + (vis[i] == 0);
		}
		sort(fre.begin(), fre.end(), cmp);
		inc(i, 0, fre.size()) {
			int nd = max(1, fre[i] - s);
			ans *= (chs[nd] - i);
			ans %= mdl;
		}
		cout << ans << endl;
	}
}
/*
2 3
1 4

*/