题目链接

主要思路还是比较好想的，一些细节公式预处理比较难搞…

参考题解

分析

从前往后遍历，如果s[]剩下的数中，s[i] < t[i]则对答案是有贡献的；
贡献就是后面位置[i+1 ~ n]的数字可以随便排，也就是带重复数字的全排列（公式看题解）；
到这里就知道了要搞一个桶来维护一下每个数字的个数，而且要维护前缀和。

计算完第i位，向后遍历时，我们的s[i]就要=t[i]了，因此每次剩下的数字中cnt[s[i]]要–；
因此动态修改查询我们可以用树状数组或线段树维护这个桶。

关键是你每次修改了cnt的话，你后面的全排列计算公式也是不一样的，这个咋搞？
我们可以一开始可以先求出公式中的分母部分(记得逆元)mu；
对于每次修改，在修改前我们先把mu除掉cnt[s[i]]，cnt[s[i]]–，然后mu再乘上cnt[s[i]]就行了；

注意最后我们还要特判s[]是t[]的前缀的情况，此时ans += 1；
题解中是从0开始的，因此是 fac[n-i-1]；
我是从1开始的，所以fac[n-i]，这个注意一下就行。

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 998244353;
//const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int s[maxn],t[maxn];
int cnt[maxn];	//s[]中每种数的个数
ll fac[maxn],infac[maxn];	//阶乘，阶乘逆元
int n,m;

struct node
{
	int l,r;
	ll v;
}tr[maxn*4];

void pushup(int u)
{
	tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
//	tr[u].v = max(tr[u<<1].v, tr[u<<1|1].v);
}

void build(int u,int l,int r)
{
	tr[u] = {l,r};
	
	if(l == r) return;

	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

void update(int u,int idx,int x)	//单点修改
{
	if(tr[u].l == idx && tr[u].r == idx)
	{
		tr[u].v += x;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(idx <= mid) update(u<<1, idx, x);
	else update(u<<1|1, idx, x);
	
	pushup(u);
}

int query(int u,int l,int r)
{
	if(l <= tr[u].l && r >= tr[u].r) return tr[u].v;
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	int ans = 0;
	if(l <= mid) ans += query(u<<1, l, r);
	if(r > mid) ans += query(u<<1|1, l, r);
	
	return ans;
}

void init()	//处理阶乘和阶乘逆元
{
	fac[0] = infac[0] = 1;
	for(int i=1;i<maxn;i++)
	{
		fac[i] = fac[i-1] * i % mod;
		infac[i] = infac[i-1] * qmi(i,mod-2,mod) % mod;
	}
}

void solve()
{
	init();
	
	iire(n,m);
	
	build(1,1,maxn-1);	//注意这里是maxn-1，不是n
	
	for(int i=1;i<=n;i++)
	{
		ire(s[i]);
		cnt[s[i]]++;
		
		update(1,s[i],1);
	}
	
	for(int i=1;i<=m;i++) ire(t[i]);
	
// 	cout<
	
	ll mu = 1;	//先把分母算好
	for(int i=1;i<maxn;i++) mu = mu * infac[cnt[i]] % mod;
	
	//下面计算贡献值
	ll ans = 0;
	int f = 1;
	for(int i=1;i<=min(n,m);i++)
	{
		ll num = query(1,1,t[i]-1);	//求出s[]剩下数字中
		ans = (ans + num*fac[n-i] % mod * mu % mod) % mod;
		
		if(cnt[t[i]])
		{
			mu = mu * fac[cnt[t[i]]] % mod;	//先除去cnt[t[i]]
			cnt[t[i]] --;
			mu = mu * infac[cnt[t[i]]] % mod;	//先乘上cnt[t[i]]
			
			update(1,t[i],-1);
		}
		else
		{
			f = 0;
			break;
		}
	}
	
	if(f && n < m) ans = (ans + 1) % mod;	//s是t的前缀
	
	cout<<ans<<'\n';
}

int main()
{
	int T;
//	ire(T);
	T = 1;
	while(T--)
	{
		solve();
	}
	
	return 0;
}


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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192