[心之碎片] - 20240817模拟赛
总结与反思B - 对于求权值总和 / 乘积 等于定值要想到背包dp
C - sgt 维护的值看看是否冗余, 只需要单点修改的东西不需要进入 up 和 dn
B - ppip 数列
ppip看到了一个各元素均为正整数、长度为k、各元素之和为n的不降数列。
他想要知道这种数列的个数，对998244853取模。
转化为 权值为 1 - k 的物品, 不限制取的个数, 总和为 n 的方案数, 转化为完全背包问题
在遇到【不易处理的限制】与【就算有限制也很好处理，可惜没限制】的问题时，可以通过转转转将其转化。
原本横向的性质，在新问题上必须纵向考虑。
对于有关【整数】、【重复】等的问题，可考虑将【有无】与【数量之差】相互转化。
f = 1;
cin >> n >> k;
n -= k;
for (int i = 1; i <= k; i++) {
for (int j = i; j <= n; j++) {
f = (f + f) % P;
}
}
cout << f;
D - P4472 八维
倍增, 哈希
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pii;
const int N = 505;
const ll B = 233;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
char s;
int n, m, K;
ll p, f;
long long same, all;
pii g;
unordered_map<ll, int> cnt;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> K;
for(int i = 0; i < n; i++){
cin >> s;
}
int lim = log2(K);
p = B;
for(int i = 1; i <= lim; i++){
p = p*p;
}
for(int d = 0; d < 8; d++){
// 录入 f, g
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
f = s;
g = make_pair((i + dx + n) % n, (j + dy + m) % m);
}
}
// 倍增
for(int k = 1; k <= lim; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int x = g.first;
int y = g.second;
f = f*p + f;
g = g;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
ll hash = 0;
auto cur = make_pair(i, j);
for(int k = lim; k >= 0; k--){
if((K >> k) & 1){
hash = hash*p + f;
cur = g;
}
}
cnt++;
}
}
}
for(auto v : cnt){
same += 1ll*v.second*v.second;
}
all = 64ll*n*n*m*m;
cout << same / __gcd(same, all) << '/' << all / __gcd(same, all);
return 0;
}
在这段描述中，你提到了两道题，以及你对解决方案的总结与反思。让我为你进一步简化和解释：
### B - ppip 数列
#### 问题描述：
你需要找到所有长度为k的、不降的正整数数列，这些数列的元素之和为n，并对结果进行取模运算。
#### 解题思路：
这个问题可以通过将其转换为完全背包问题来解决：
1. 视每个数列元素为背包中的物品，每个物品的权值为1到k。
2. 求权值总和为\(n - k\)的方案数。
#### 解决方法：
使用动态规划来解决背包问题。你的思路是正确的，可以通过完全背包的DP实现。
#### 示例代码：
#include <iostream>
#include <vector>
#define MOD 998244853
using namespace std;
int main() {
int n, k;
cin >> n >> k;
n -= k;
vector<int> dp(n + 1, 0);
dp = 1;
for (int i = 1; i <= k; ++i) {
for (int j = i; j <= n; ++j) {
dp = (dp + dp) % MOD;
}
}
cout << dp << endl;
return 0;
}
### C - sgt 维护的值看看是否冗余
你提到`sgt`（线段树）需要维护的值时，需要确认是否存在冗余。对于只需要单点修改的情况，不需要进入`up`和`dn`。
### 总结：
1. **转化思路** - 对于不容易处理的复杂限制条件，可以尝试通过不同的角度（例如横向与纵向转换）来简化问题。
2. **背包问题** - 遇到求解和或积等于某定值的问题时，可以通过背包DP的方式来解决。
3. **数据结构优化** - 在使用数据结构如线段树时，确保操作的值没有冗余，优化复杂度。对于单点修改，只需要更新相关节点，不需要进行其他多余操作。
希望这些解答能帮助你更清晰地理解和解决这些问题！如果还有其他不明白的地方，随时提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_256:}{:10_256:} 666 666 {:7_142:} 闻币而来
{:10_256:} 👌
{:7_113:}币
{:10_254:}{:10_254:}看看 谢谢
页:
[1]