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

题目大意：

CF1648C Tyler and String
大意：给两个数组(2e5)，要求将第一个数组任意排列之后其字典序大小小于第二个，问这样的排列的个数。

解：

显然，字典序小于对于每一位来讲，要么第一个数组的第一位就小于第二个数组的第一位，要么第一位上两个数组相等，然后在第二位有同样的区别，以此类推。
如果在一位上第一个数组小于第二个的话，那么剩下的数位就可以随意排列了，如果相同的话，就递推到下一位，注意在递推的过程中，我们的数集里实际上损失了一个等于第二个数组当前位置上的数。
要想O1或者Ologn地将“小于该位上的数的数量”计算出来，容易想到前缀和，然而由于递推的时候会损失一个数，不适合修改的前缀和无法胜任，这时候就想到了用线段树去维护前缀和，损失一个数时相当于比它大的数的前缀和全部-1。
还有另外的细节……由于要求不同排列的个数，所以要去计算数位的重复性，使用通常的算完结果之后再去除以重复数量会返回错误，为什么呢？是因为在递推的时候不能简单地看作仅仅损失了一个数，如果计算重复的话，在这个时候损失的数其实可能是等同于该数数量的数中的任意一个，所以我们需要创建一个adder，每次递推都乘上这个个数，为的是保证所有重复的情况都被计算，这样一来才能在除以总重复次数时返回正确结果。
然后还有个特殊情况，当递推到最后数组1和数组2的每一位都相等，而数组2还有剩余，这样的话数组1是更小的，于是要在最后的结果上加上一个1。
然后出现了世界名画：Output 998244353 Answer:0
不愧是你，CF。
本题其实好像和dp没啥关系啊，不是纯data structure吗……
嗯，不过一开始想到这个思路确实是借助dp的思维形式的，所以也加入到全家桶里了，算是比较水的一题1900。

代码

代码
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
114
115
116
117
118
119

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::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(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
ll fv[maxn], inv[maxn];
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;
}
void getf(int n) {
	ll tmp = 1;
	inc(i, 1, n + 1) {
		fv[i] = tmp;
		tmp *= i + 1;
		tmp %= mdl;
	}
}
ll a[maxn * 4], temp[maxn], ad[4 * maxn],cnt[maxn];
void addq(ll o, ll l, ll r,ll x,int ql,int qr) {
    if (ql <= l && r <= qr) {
        a[o] += (r - l + 1) * x;
        ad[o] += x;
        return;
    }
    int m = (l + r) / 2;
    int ls = 2 * o, rs = 2 * o + 1;
    if (ql <= m) addq(ls, l, m,x,ql,qr);
    if (m < qr) addq(rs, m + 1, r, x,ql,qr);
    a[o] = a[ls] + a[rs] + (r - l + 1) * ad[o];
}

ll query(ll o, ll l, ll r, ll d,ll ql,ll qr) {
    if (qr == 0)return 0;
    //cout << ql << " " << qr << endl;
    if (ql <= l && r <= qr) return a[o] + d * (r - l + 1);
    ll m = (l + r) / 2;
    ll ls = 2 * o, rs = 2 * o + 1;
    ll ret = 0;
    if (ql <= m) ret += query(ls, l, m, d + ad[o],ql,qr);
    if (m < qr) ret += query(rs, m + 1, r, d + ad[o],ql,qr);
    return ret;
}
int main() {
    fv[0] = 1;
    int n, m;
    cin >> n >> m;
    ll cst = 200002;
    getf(cst);
    inc(i, 0, n) {
        ll tmp;
        cin >> tmp;
        cnt[tmp]++;
        addq(1, 1, cst,1,tmp + 1, cst);
    }
    ll res = 0;
    int f = 0;
    ll adder = 1;
    inc(i, 0, m) {
        
        ll tmp;
        cin >> tmp;
        if (i >= n) {
            f = 1;
            continue;
        }
        ll les = query(1, 1, cst, 0, tmp, tmp);
      //  cout << "les=" << les << endl;
        res += adder*les %mdl* fv[n - i - 1] % mdl;
        res %= mdl;
        ll jud = query(1, 1, cst, 0, tmp + 1, tmp + 1) - les;
        if (jud == 0)break;
      //  cout << "jud=" << jud << endl;
      //  cout << "adder=" << adder << endl;
       // cout << "res=" << res << endl;
        adder *= jud;
        adder %= mdl;
        addq(1, 1, cst, -1, tmp + 1, cst);


​        
​    }
​    inc(i,1,cst+1){
​        if (cnt[i] > 1) {
​            res *= cpow(fv[cnt[i]], mdl - 2);
​            res %= mdl;
​        }
​    }
​    ll ans = res + f;
​    ans %= mdl;
​    cout << ans;
}