2019CCPC 哈尔滨 I Interesting Permutation（计数dp)

题意：定义 f i = m a x ( a 1 , a 2 , . . . a i ) , g i = m i n ( a 1 , a 2 , . . . a i ) , h i = f i − g i f_i=max(a_1,a_2,...a_i), g_i=min(a_1,a_2,...a_i),h_i=f_i-g_i fi​=max(a1​,a2​,...ai​),gi​=min(a1​,a2​,...ai​),hi​=fi​−gi​，现给定一组 h i h_i hi​，求满足该 h i h_i hi​的排列数。 题解摘自官方题解。

#include
using namespace std;
#define ll long long
const int maxn=100010;
const int mod=1e9+7;

int a[maxn],n;
ll dp[maxn];
int main(){
    int t;scanf("%d",&t);
    a[0]=0;
    while(t--){
        scanf("%d",&n);
        bool flag=1;
        for(int i=1;i