2019.10.24 CSP%你赛第二场d1t3
题目描述 Description
精灵心目中亘古永恒的能量核心崩溃的那一刻，Bzeroth 大陆的每个精灵都明白，他们的家园已经到了最后的时刻。
就在这危难关头，诸神天降神谕，传下最终兵器——潘少拉魔盒。然而当精灵们准备打开魔盒时，魔盒的守护灵出现在精灵们面前：“如果你们想要拯救世界，必须要先解决这个困难的问题：定义一个 N 阶数列 A 为神奇数列当且仅当对所有2≤i≤N−1 ，都有 Ai−1+Ai+1≥2×Ai。现在有一个N阶正整数列B ，请计算将 B 数列均匀随机打乱之后，得到的数列是神奇数列的概率 P 。你只需要输出P×(N!)mod998244353 的结果即可。（显然 P×(N!) 一定是个整数）。”
输入描述 Input Description
第一行为 1 个正整数 N。
第二行为 N 个正整数 Ai。
输出描述 Output Description
输出 P×(N!)mod998244353 的结果。
样例输入 Sample Input
4
1 2 1 3
样例输出 Sample Output
8数据范围及提示 Data Size & Hint
对于 50%的数据：3 ≤ N ≤ 10。
对于 80%的数据：3 ≤ N ≤ 20。
对于 100%的数据：3 ≤ N ≤ 40，1≤Ai≤109 。
容易知道，这个题实际上是想让我们求给定的集合能够拼成多少个神奇数列。
经过推一波式子，我们可以知道a[i+1]-a[i]>=a[i]-a[i-1]，所以它的差分序列单调递增，即其为一个下凸函数。。
因此，对于一个神奇数列，满足它一定是一个下凸函数。
考虑在这个函数上进行dp:
对于一个区间dp[i][k]，表示区间最左端取值为a[i]，最右端取值为a[k]，则进行转移时每次往左端或右端放入一个点。
但是由于刚才的式子，我们必须记录端点之前的位置的取值，所以我们用dp[i][j][k][l]表示某个下凸函数的一段区间最左端取值为a[i],a[j]，最右端取值为a[l],a[k]的神奇序列个数。
考虑将原来的集合排序，所以易知下凸函数的顶点一定是整个集合的最小值。
由此，我们每次考虑放入一个新值a[pos]满足pos=max(i,k)+1，原因是排好序的序列单调递增，又因为a[i],a[k]一定含有当前区间值最大的点（因为是下凸函数），所以我们只需要取二者下标最大值+1作为新值下标。所以可以用刚才的方法检验是否答案合法。
上代码：
#include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<cstring> #include<cstdio> using namespace std; typedef long long LL; #define mem(a,b) memset(a,b,sizeof(a)) typedef pair<int,int> PII; typedef pair<int,PII> PIP; const int MOD=998244353,maxn=42; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } int n,a[maxn],sum=1,jc[maxn],dp[maxn][maxn][maxn][maxn],ans; int main() { n=read(); jc[0]=1; for(int i=1;i<=n;i++)a[i]=read(),jc[i]=((LL)jc[i-1]*(LL)i)%MOD;//阶乘预处理 sort(a+1,a+n+1); for(int i=2;i<=n;i++) { if(a[i]!=a[i-1])break; sum++; }//取出区间最小值 for(int i=sum+1;i<=n;i++)a[i-sum+1]=a[i];//把其它最小值扔到后面 dp[1][0][1][0]=1; n=n-sum+1;//去掉与最小值相同的值 for(int i=1;i<=n;i++) for(int j=0;j<i;j++) for(int k=1;k<=n;k++) for(int l=0;l<k;l++) { int pos=max(i,k)+1;//找到新加入的数 if(pos==n+1){ans=(ans+dp[i][j][k][l])%MOD;continue;}//如果整个下凸函数已经构成了长度为n的区间 if(2*a[i]<=a[pos]+a[j] || i==1)dp[pos][i][k][l]=(dp[pos][i][k][l]+dp[i][j][k][l])%MOD;//检查i端是否合法 if(2*a[k]<=a[pos]+a[l] || k==1)dp[i][j][pos][k]=(dp[i][j][pos][k]+dp[i][j][k][l])%MOD;//检查k端是否合法 } printf("%d\n",((LL)ans*(LL)jc[sum])%MOD);//因为最小值一共有sum个取值，所以这sum个取值进行全排列再乘以答案即可 return 0; }