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;
}