Arrange
Accepts: 221
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
问题描述
Cupid一不小心将爱情之箭射到了自己，他爱上了Psyche。
这引起了他的母亲Venus的注意。Venus将Psyche带到了一堆打乱的谷堆旁。
这儿共有n 堆稻谷，编号为1 到n。Psyche需要将这些谷堆以某种顺序排列，设最终排在第i 位的谷堆是 Ai。
她得知了一些该排列的要求：
1. 对于任意整数i∈[1,n] A1,A2,...,Ai的最小值为Bi
2. 对于任意整数i∈[1,n] A1,A2,...,Ai的最大值为Ci
现在Psyche想知道，共有多少种合法的排列。由于答案可能很大，输出时对998244353 取模。
输入描述
第一行，一个整数T (1≤T≤15)代表数据组数。
对于每组数据，第一行有一个整数n (1≤n≤105) ，代表排列大小。
第二行，n 个整数，第i 个整数为Bi B_i Bi (1≤Bi≤n)
第三行，n 个整数，第i 个整数为Ci C_i Ci (1≤Ci≤n)
输出描述
输出T 行，对于每组数据输出答案对998244353 取模的结果。
输入样例
2 3 2 1 1 2 2 3 5 5 4 3 2 1 1 2 3 4 5
输出样例
1 0
Hint
对于第一组数据，只有一种合法的排列(2,1,3)
对于第二组数据，没有合法的排列。
题意：中文题意 长度为n的序列 b[i] 代表前i个数的最小值 c[i]代表前i个数的最大值 问有多少种合法的排列
题解：考虑只有当b[j]==b[j-1]&&c[j]==c[j-1])的时候才有贡献
但是注意1~n的数只能出现一次 这就是gg的作用
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<algorithm> 9 #define ll __int64 10 #define mod 1e9+7 11 #define PI acos(-1.0) 12 using namespace std; 13 int t; 14 ll b[100005]; 15 ll c[100005]; 16 int n; 17 int main() 18 { 19 while(scanf("%d",&t)!=EOF) 20 { 21 for(int i=1; i<=t; i++) 22 { 23 scanf("%d",&n); 24 for(int j=1; j<=n; j++) 25 scanf("%I64d",&b[j]); 26 for(int j=1; j<=n; j++) 27 scanf("%I64d",&c[j]); 28 if(b[1]!=c[1]) 29 { 30 printf("0 "); 31 continue; 32 } 33 ll ans=1; 34 ll m=1; 35 ll gg=1;//注意 36 for(int j=2; j<=n; j++) 37 { 38 if(b[j]>b[j-1]||c[j]<c[j-1]) 39 { 40 m=0; 41 continue; 42 } 43 else 44 { 45 if(b[j]!=b[j-1]&&c[j]!=c[j-1]) 46 { 47 m=0; 48 continue; 49 } 50 else 51 { 52 if(b[j]!=b[j-1]||c[j]!=c[j-1]) 53 gg++; 54 else 55 { 56 ans*=(c[j]-gg-b[j]+1); 57 gg++; 58 ans%=998244353; 59 } 60 } 61 } 62 } 63 if(m) 64 printf("%I64d ",ans); 65 else 66 printf("0 "); 67 } 68 } 69 return 0; 70 }