题解分享
题解分享简介
元素祭坛的激活挑战 - 题解
动规：
求每个k级排列，k级排列肯定是从k-1级排列生成的，相当于只需要看有没有k这个数字，有的话就能从k-1状态转换过来。
状态转移方程：
dp[k] = dp[k-1] cnt[k]
cnt[k]代表的是k出现的次数，dp状态和k出现次数相乘就是组合数。
```
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int n;
cin>>n;
int a[n+1];
unordered_map<int, int> cnt;
long long dp[n+1] = {1};
for(int i = 0;i<n;i++)
{
cin>>a[i];
cnt[a[i]]++;
}
long long res = 0;
for(int i = 1;i<=n;i++)
{
if(!cnt.count(i)) break; //出现次数为0的话后面都不可能生产排列了
dp[i] = dp[i-1]*cnt[i]%mod;
res = (res + dp[i])%mod;
}
cout<<res;
}
```
查看全文
0
0
1
3
