一个 1 到 n 的排列被称为半递增序列,是指排列中的奇数位置上的值单调递增,偶数位置上的值也单调递增。
不要被题目骗了,其实这个问题就是n选n/2的组合问题,组合可以用杨辉三角推导,然后就是求余a=b+c=>a%k=(b%k+c%k)%k
public class Main {
public static void main(String[] args) {
Main main = new Main();
System.out.println(main.getCombine(10000));
}
private int getCombine(int n){
if(n==1)
return 1;
int k = n/2;
int[] dp = new int[n+1];
for(int i = 1; i <= n; i++){
dp[0]=1;
dp[i]=1;
for(int j = i-1; j>=1; j--){
dp[j]=dp[j-1]+dp[j];
dp[j]%= (1e9+7);
}
}
return dp[k];
}
}