码蹄周赛第19场(入门组) 0天00:31:35 完成竞赛 题目 提交记录 个人排名 高校排名 1、排斥序列 时间限制:1秒 占用内存:64 M 给定一个长度为nn的非负整数序列b1,b2,…,bnb,b,…,b,求长度为nn的非负整数序列aa的个数,满足序列aa中的数字两两不同,且对于任意 1≤i≤n1≤i≤n,ai≤bia≤b。 格式 输入格式: 第一行输入一个整数n(1≤n≤105)n(1≤n≤10),表示序列长度。 第二行输入nn个整数b1,b2,…,bn(0≤bi≤109)b,b,…,b(0≤b≤10)。 输出格式: 输出满足条件的序列aa的个数。由于答案可能会很大,你只需要输出对109+710+7取模后的结果。 样例 1 输入: 4 1 3 2 3复制 输出: 8复制 备注 对于样例一,88种方案如下: [0,1,2,3],[0,2,1,3],[0,3,1,2],[0,3,2,1],[1,0,2,3],[1,2,0,3],[1,3,0,2],[1,3,2,0][0,1,2,3],[0,2,1,3],[0,3,1,2],[0,3,2,1],[1,0,2,3],[1,2,0,3],[1,3,0,2],[1,3,2,0]
时间: 2025-06-02 20:41:26 浏览: 24
### 计算满足条件的非负整数序列个数
#### 问题解析
此问题是典型的计数组合学问题,目标是找到长度为 \( n \) 的非负整数序列 \( a \),其中每个元素 \( a_i \) 都小于等于对应给定序列 \( b \) 中的元素 \( b_i \)[^1]。此外,\( a \) 序列中的所有数字必须互不相同。为了有效解决问题并避免重复计算,可以采用动态规划或回溯的方法。
#### 动态规划解决方案
以下是基于动态规划的思想来解决这个问题的一个具体实现方法:
1. **状态定义**
定义 `dp[mask][last]` 表示当前已经选择了哪些索引(由掩码 mask 表示),最后一个选择的值为 last 的情况下,剩余的选择方案总数[^2]。
2. **初始状态**
初始化时,设置所有的 dp 数组值为零,并设定边界条件以便后续递推使用。
3. **状态转移方程**
对于每一个新的位置 i 和可能选取的新值 v (v ≤ bi),尝试更新 dp 状态:
```cpp
if (!(mask & (1 << j)) && v != last){
next_mask = mask | (1 << j);
dp[next_mask][v] += dp[mask][last];
dp[next_mask][v] %= MOD;
}
```
4. **最终结果**
所有的合法路径总和可以通过累加所有完整的 mask 下的状态值得到。
下面是具体的 C++ 实现代码片段:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
const int MOD = 1e9 + 7;
long long dp[1<<MAXN][MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
vector<int> b(n);
for(auto &x : b) cin >> x;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1; // Initial state with no elements selected.
for(int mask=0; mask<(1<<n); ++mask){
for(int last=0; last<=n; ++last){
if(!dp[mask][last]) continue;
for(int j=0; j<n; ++j){
if(mask & (1<<j)) continue; // Already used index j
for(int val=0; val<=min(last-1,b[j]); ++val){
int newMask = mask | (1<<j);
dp[newMask][val] = (dp[newMask][val] + dp[mask][last]) % MOD;
}
}
}
}
long long result = 0;
for(int m=(1<<n)-1; m>=0; --m){
for(int l=0;l<=n;++l){
result = (result + dp[m][l])%MOD;
}
}
cout << result;
}
```
#### 复杂度分析
时间复杂度主要取决于状态的数量以及每次状态转移所需的时间开销。由于共有 \( O(2^n * n) \) 种状态,每种状态下最多执行 \( O(n*b_{max}) \) 次操作,整体复杂度大约为 \( O((2^n)*n*b_{max}) \)[^3]。
---
###
阅读全文
相关推荐
















