CF1698E

发表于 | 分类于 |

题面:https://codeforces.com/contest/1698/problem/E

大致题意:给定a排列、b排列的部分、数值s，规定可对a排列进行如下操作:在第i次操作时，可选定下标范围在i~i+s的两个数值，进行交换(若选定的两个下标相同，则排列不变，可视为跳过一次操作)

求通过若干次操作，能使a排列变为b排列的b排列总数

题解:易想到，先求解怎样的b排列符合条件，即假定一个特定的b排列，判断是否满足条件。先上结论:若，则符合条件

证明如下:

  1. 证明:将b按大小与a一起重排后，按照新的排列考虑问题不影响结果(因为a数组已经固定，故可以理解为对a数组进行重新”投射”)
  2. 按的大小从小到大考虑问题，若=m,大于m，则前几次操作不会涉及(因为其大于m,与前面的b不会对应);若，则不需移动，且第i次操作可直接放弃而不造成影响;若，此时a中的m所对应b大于m，则在考虑中，已将其调到另外一个b处，必定可以完成操作
  3. 欲证明，若=m,大于m，则使a归位需要的s最少为a、b之差，按b大小重排后则所需，等效到原排列中s不变
  4. 已知s，对每个未知b，可知道其可能值的个数(可能值从小到大排)，故从可能值个数较小的b开始考虑
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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/

ll T, n, m, k, tt = 0, ss;
ll tmp, a[300005], b[300005];
const ll mod = 998244353;
// 1 0
// 2 0
// 3 1
// 4 1
// 5 2
// 6 2
// 7 3
void solve()
{
    ll ans = 1;
    bool flag = 1;
    cin >> n >> ss;
    set<ll> s;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(i);
    }
    for (ll i = 1; i <= n; i++)
    {
        cin >> b[i];
        if (b[i] != -1)
        {
            if (a[i] - b[i] > ss)
            {
                flag = 0;
            }
            s.erase(b[i]);
        }
    }
    if(!flag)
    {
        cout << "0\n";
        return;
    }
    vector<ll> cnt;
    vector<ll> s2(s.begin(), s.end());
    sort(s2.begin(), s2.end());
    for (ll i = 1; i <= n;i++)
    {
        if(b[i]==-1)//b>=a[i]-s
        {
            ll tmp = s2.end()-lower_bound(s2.begin(), s2.end(),a[i]-ss);
            //cout << tmp << "\n";
            cnt.push_back(tmp);
        }
    }
    ll tmp = 0;
    sort(cnt.begin(), cnt.end());
    for(auto e:cnt)
    {
        ans = ans * ((e - tmp)%mod);
        ans %= mod;
        tmp++;
        tmp %= mod;
    }
    cout << (ans+mod)%mod << "\n";
}
int main()
{
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

码力太弱哩，就嗯写，时间复杂度大概是nlogn