CS Academy Restricted Permutations

题目链接：https://csacademy.com/contest/archive/task/restricted-permutations

题目大意：求在约束条件下1~N的全排列的个数。约束：0， 1表示的n - 1个数，1表示第i个数一定要放到第i+1个数的前面，0反之。

解题思路：我也是看的editorial。。。实际上当我们考虑第i+1个数的时候我们只需要考虑他与第i个数的关系就可以了，那么这样子我们就可以设dp[i][j]表示第i个数在位置j的时候前i个数的全排列个数。那么：

i在i-1后面：dp[i][j] = dp[i- 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 1]

i在i-1前面：dp[i][j] = dp[i - 1][i - 1] + dp[i - 1][i - 2] + ... + dp[i - 1][j + 1]

朴素写法O(n³)，可以记录dp[i- 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 1]降低到O(n²)

代码：

 1 const int maxn = 2e3 + 5;
 2 int sta[maxn], n;
 3 ll dp[maxn][maxn];
 4 
 5 void solve(){
 6     memset(dp, 0, sizeof(dp));
 7     dp[1][1] = 1; 
 8     ll lasum;
 9     for(int i = 2; i <= n; i++){
10         if(sta[i]){
11             lasum = dp[i - 1][0];
12             for(int j = 1; j <= i; j++){
13                 dp[i][j] += lasum % mod;
14                 lasum += dp[i - 1][j] % mod;
15             }
16         }
17         else{
18             lasum = 0;
19             for(int j = i; j >= 1; j--){
20                 dp[i][j] += lasum % mod;
21                 lasum += dp[i - 1][j - 1] % mod;
22             }
23         }
24     }
25     ll ans = 0;
26     for(int i = 1; i <= n; i++) ans += dp[n][i] % mod;
27     printf("%I64d
", ans % mod);
28 }
29 
30 int main(){
31     scanf("%d", &n);
32     for(int i = 2; i <= n; i++) scanf("%d", &sta[i]);
33     solv

题目：

Restricted Permutations

Time limit: 1000 ms
Memory limit: 128 MB

Find the number of permutations of size

Standard input

The first line contains a single integer

The second line contains a binary array of size $i^{th}ith element of this array is 11 if ii comes before i+1i+1 in the permutation, 00 otherwise.$

Standard output

Print the answer modulo $10^9+7109+7 on the first line.$

Constraints and notes

Input	Output	Explanation
3 1 0	2	1 2 3 1 3 2 3 1 2
5 1 1 0 1	9	1 2 3 4 5 6 7 8 9 10 1 2 4 3 5 1 2 4 5 3 1 4 2 3 5 1 4 2 5 3 1 4 5 2 3 4 1 2 3 5 4 1 2 5 3 4 1 5 2 3 4 5 1 2 3
7 1 0 1 0 1 0	272