格点染色

NC233443. 格点染色

描述

有 $n$ 个格子，当你位于第 $x$ 个格子时，你可以进行以下两种操作：

走到第 $x+1$ 个格子。
如果第 $x$ 个格子未被染上色，把第 $x$ 个格子染成黑色，然后跳到第 $a_x$ 个格子。

现在你要从第 $1$ 个格子开始，回答把所有格子染成黑色的顺序有多少种。
答案对 $10^9+7$ 取模。

输入描述

第一行一个正整数  。
第二行包括  个整数，第  个数表示 。保证  单调不降。

输出描述

输出一行包括一个整数，表示答案对  取模后的值。

示例1

输入:

3
1 1 2

输出:

说明:

样例中以下四种顺序是可能出现的：
$[1,2,3]$ ， $[1,3,2]$ ， $[2,1,3]$ ， $[3,2,1]$ 。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 141ms, 内存消耗: 412K, 提交时间: 2022-05-13 19:29:16

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
	int n,s=1;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),s=1ll*s*(i-x+1)%mod;
	cout<<s;
}

Python3 解法, 执行用时: 1081ms, 内存消耗: 122452K, 提交时间: 2022-05-13 19:50:03

n = int(input())
nums = [int(x)-1 for x in input().split()]
acc = 1
for idx, num in enumerate(nums):
    res = (idx-nums[idx]+1) * acc
    acc = res % (10 ** 9 + 7)
print(acc)