Codeforces Round 1042 (Div. 3) G Wafu! 题解

题意：每一次操作删除集合中最小的元素 x，并产生新的 x - 1 个元素值分别为 1 2 3 … x - 1 放入集合之中。 每次操作一个数 x 可以使得最终答案乘上 x，问我们操作 k 次在模 1e9 + 7 的基础上最终得到的答案是多少，每个询问独立。

---

思路：我们不妨先观察一个数 x 最终需要操作的次数以及能给我们带来的贡献。

首先看操作次数：1 : 1次 、 2 : 2 次、 3 : 4 次、 4 : 8 次 (2^(x - 1)次)

其次看贡献：1 : f(1) = 1 、 2 : f(2) = 2 * f(1) = 2 、 3 : f(3) = 3 * f(2) * f(1) 、4 : f(4) = 4 * f(3) * f(2) * f(1) 我们会发现我们后面的 f(1) * f(2) * f(3) … 可以用一个前缀乘来维护。因此我们可以写一个预处理

dp[0] = 1;
int res = 1; // 统计前缀成
for(int i = 1; i <= 30; i ++){dp[i] = i * res % mod;res = res * dp[i] % mod;
}

那么我们可以针对每个测试中的所有元素进行一次排序，因为我们每次必须选取最小的元素删除。然后模拟即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int dp[N];
int a[N];
void solve(){int n, k;cin >> n >> k;for(int i = 1; i <= n; i ++){cin >> a[i];}sort(a + 1, a + 1 + n);int ans = 1;for(int i = 1; i <= n && k; i ++){if(a[i] < 31 && (1 << (a[i] - 1)) <= k){ans = ans * dp[a[i]] % mod;k -= (1 << (a[i] - 1));}else{int x = 1; // a[i] 拆成 1 ~ i - 1ans = ans * a[i] % mod;k --;while(k){if(1 << (x - 1) <= k){k -= 1 << (x - 1);ans = ans * dp[x] % mod;x ++;}else{ans = ans * x % mod;x = 1;k --;}}break;}	}cout << ans << endl;
}
signed main(){// 1 : f(1) = 1 * 1// 2 : f(2) = 2 * f(1)// 3 : f(3) = 3 * f(2) * f(1)// 4 : f(4) = 4 * f(3) * f(2) * f(1)dp[0] = 1;int res = 1;for(int i = 1; i <= 30; i ++){dp[i] = i * res % mod;res = res * dp[i] % mod;}int T;cin >> T;while(T --){solve();}return 0;
}