Fork me on GitHub

「hihocoder1596」Beautiful Sequences

发表于 | 分类于
字数统计: 744字 | 阅读时长 ≈ 4分钟

Links there:hihocoder-1596

题意

对于一个正整数列 $ a[1], … , a[n] (n ≥ 3) $，如果对于所有 $2 ≤ i ≤ n - 1$ ，都有 $a[i-1] + a[i+1] ≥ 2 × a[i]$ ，则称这个数列是美丽的。

现在有一个正整数列 $b[1], …, b[n]$ ，请计算:将 $b$ 数列均匀随机打乱之后，得到的数列是美丽的概率 $P$。

你只需要输出 $(P × (n!)) $ $ mod \space 1000000007$ 即可。（显然 $P × (n!)$ 一定是个整数）

思路

将${ a_i}$转化为维护一个凸函数的图像 用$f[i][j][k][t]$ 表示当前第 $i$ 个,左端点最大值和次大值为 $a[i],a[j]$ ,右端点最大值为 $a[k]$ , 次大值 $a[t]$ 的方案.由于已经排过序,新加进来的 $契$ 一定比当前左右端点的都要大.

那么有两种情况,要么在左边成立 要么在右边成立.

这第二个柿子有一点奇怪 但是因为左边端点其实是和右边端点等价的. 所以可以将上面第二个写成这样

注意细节将所有最小的计数 然后答案去乘它的阶乘.

Code

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
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
int n,b[61],f[61][61][61][61],ans = 1;
const int Mod = 1e9+7;
inline bool isok(int a,int x,int y){
    return (2*b[x] <= b[a] + b[y]);
}
inline void upd(int &x,int y){x=(x+y)%Mod;}
///------------------head------------------
signed main(signed argc, char *argv[]){
    // freopen("data.in","r",stdin);
    // freopen("data.ans","w",stdout);
    n=read();
    rep(i,1,n) b[i]=read();
    sort(b+1,b+n+1);
    int ll = b[1],l = 0;
    rep(i,1,n) {if (ll == b[i]) ++l,ans = ans * i % Mod;}
    if (l == n) {
        printf("%lld\n",ans); return 0;
    }
    cerr << ans << endl;
    f[l][l][l][l] = 1;
    for (int i = l; i <= n - 1; ++i)
        for (int j = 1; j <= i; ++j)
            for (int k = 1; k <= i; ++k)
                for (int t = 1; t <= i; ++t) {
                    if (!f[i][j][k][t]) continue;
                    int del = f[i][j][k][t];
                    upd(f[i+1][i][k][t],del * isok(i+1,i,j));
                    upd(f[i+1][k][i][j],del * isok(i+1,k,t));
                }
    int ans2 = 0;
    for (int j = 1; j <= n; ++j)
        for (int k = 1; k <= n; ++k)
            for (int t = 1; t <= n; ++t)
            upd(ans2,f[n][j][k][t]);
    ans2 = ans2 * ans % Mod;
    printf("%lld\n",ans2);
    return 0;
}

/* Examples: */
/*

*/

/*

*/