MYF

HDU 5719 Arrange

Posted on | In | | Visitors

题目链接

HDU 5719

解题方法：乘法原理

题目分析

题目大意

一个数列由1~N组成，已知A1～Ai的最小值为Bi、最大值为Ci，问该数列共有多少种可能

解析

官方解析：

首先，根据题意可得B数组应是单调不升的，C数组是单调不降的。

可以发现$ A_1 = B_1 = C_1 $，所以如果$ B_1 \neq C_1 $无解。

进一步，我们发现如果$ Bi < B{i-1} $，$ A_i = B_i $；如果$ Ci > C{i-1} $，$ A_i = C_i $。但是如果$ Bi < B{i-1} $和$ Ci > C{i-1} $同时满足，就会产生冲突导致无解。

考虑$ Bi = B{i-1} $和$ Ci = C{i-1} $同时满足的情况，此时应有$ A_i \in (B_i,C_i) $且$ A_i $没有在之前使用过。因为$ (B_i,C_i) $是不断变大的，我们只需维护一下这个区间内有多少值已经被使用过了，用乘法原理统计答案即可。注意到如果某时刻$ A_i $没有值可以使用，也会导致无解。

时间复杂度$ O(Tn) $。

代码

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
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int b[maxn],c[maxn];
int t,n;
int main(){
    scanf("%d",&t);
    while (t--) {
        
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d",b+i);
        }
        for (int i=1; i<=n; i++) {
            scanf("%d",c+i);
        }
        
        if (b[1]!=c[1]) {
            cout<<0<<endl;
            continue;
        }
        ll ans=1;
        for (int i=2,cnt=1; i<=n; i++) {
            if (b[i]==b[i-1]&&c[i]==c[i-1]) {
                ans*=(c[i]-b[i]+1-cnt)%mod;
                ans%=mod;
                cnt++;
            }
            else if (b[i]<b[i-1]&&c[i]==c[i-1]){
                cnt++;
            }
            else if (b[i]==b[i-1]&&c[i]>c[i-1]){
                cnt++;
            }
            else{
                ans=0;
                break;
            }
        }
        cout<<ans<<endl;
    }
}