[心之碎片] - 20240817模拟赛

柿子饼同学

总结与反思

B - 对于求权值总和 / 乘积 等于定值要想到背包dp

C - sgt 维护的值看看是否冗余, 只需要单点修改的东西不需要进入 up 和 dn

B - ppip 数列
ppip看到了一个各元素均为正整数、长度为k、各元素之和为n的不降数列。
他想要知道这种数列的个数，对998244853取模。

转化为 权值为 1 - k 的物品, 不限制取的个数, 总和为 n 的方案数, 转化为完全背包问题

在遇到【不易处理的限制】与【就算有限制也很好处理，可惜没限制】的问题时，可以通过转转转将其转化。
原本横向的性质，在新问题上必须纵向考虑。
对于有关【整数】、【重复】等的问题，可考虑将【有无】与【数量之差】相互转化。

1. f[0] = 1;
   
2.     cin >> n >> k;
   
3.     n -= k;
   
4. 
   
5.     for (int i = 1; i <= k; i++) {
   
6.         for (int j = i; j <= n; j++) {
   
7.             f[j] = (f[j] + f[j - i]) % P;
   
8.         }
   
9.     }
   
10. 
    
11.     cout << f[n];

复制代码

D - P4472 [BJWC2018] 八维
倍增, 哈希

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef unsigned long long ll;
   
5. typedef pair<int, int> pii;
   
6. 
   
7. const int N = 505;
   
8. const ll B = 233;
   
9. const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
   
10. const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
11. 
    
12. char s[N][N];
    
13. int n, m, K;
    
14. ll p[N], f[N][N][30];
    
15. long long same, all;
    
16. pii g[N][N][30];
    
17. unordered_map<ll, int> cnt;
    
18. 
    
19. int main(){
    
20.     ios::sync_with_stdio(0);
    
21.     cin.tie(0);
    
22. 
    
23.     cin >> n >> m >> K;
    
24.     for(int i = 0; i < n; i++){
    
25.         cin >> s[i];
    
26.     }
    
27. 
    
28.     int lim = log2(K);
    
29.     p[0] = B;
    
30.     for(int i = 1; i <= lim; i++){
    
31.         p[i] = p[i - 1]*p[i - 1];
    
32.     }
    
33. 
    
34.     for(int d = 0; d < 8; d++){
    
35.         // 录入 f, g
    
36.         for(int i = 0; i < n; i++){
    
37.             for(int j = 0; j < m; j++){
    
38.                 f[i][j][0] = s[i][j];
    
39.                 g[i][j][0] = make_pair((i + dx[d] + n) % n, (j + dy[d] + m) % m);
    
40.             }
    
41.         }
    
42. 
    
43.         // 倍增
    
44.         for(int k = 1; k <= lim; k++){
    
45.             for(int i = 0; i < n; i++){
    
46.                 for(int j = 0; j < m; j++){
    
47.                     int x = g[i][j][k - 1].first;
    
48.                     int y = g[i][j][k - 1].second;
    
49. 
    
50.                     f[i][j][k] = f[i][j][k - 1]*p[k] + f[x][y][k - 1];
    
51.                     g[i][j][k] = g[x][y][k - 1];
    
52.                 }
    
53.             }
    
54.         }
    
55. 
    
56.         for(int i = 0; i < n; i++){
    
57.             for(int j = 0; j < m; j++){
    
58.                 ll hash = 0;
    
59.                 auto cur = make_pair(i, j);
    
60. 
    
61.                 for(int k = lim; k >= 0; k--){
    
62.                     if((K >> k) & 1){
    
63.                         hash = hash*p[k] + f[cur.first][cur.second][k];
    
64.                         cur = g[cur.first][cur.second][k];
    
65.                     }
    
66.                 }
    
67. 
    
68.                 cnt[hash]++;
    
69.             }
    
70.         }
    
71.     }
    
72. 
    
73.     for(auto v : cnt){
    
74.         same += 1ll*v.second*v.second;
    
75.     }
    
76.     all = 64ll*n*n*m*m;
    
77. 
    
78.     cout << same / __gcd(same, all) << '/' << all / __gcd(same, all);
    
79. 
    
80.     return 0;
    
81. }

复制代码

FishC

在这段描述中，你提到了两道题，以及你对解决方案的总结与反思。让我为你进一步简化和解释：

### B - ppip 数列

#### 问题描述：
你需要找到所有长度为k的、不降的正整数数列，这些数列的元素之和为n，并对结果进行取模运算。

#### 解题思路：
这个问题可以通过将其转换为完全背包问题来解决：
1. 视每个数列元素为背包中的物品，每个物品的权值为1到k。
2. 求权值总和为\(n - k\)的方案数。

#### 解决方法：
使用动态规划来解决背包问题。你的思路是正确的，可以通过完全背包的DP实现。

#### 示例代码：

1. #include <iostream>
   
2. #include <vector>
   
3. #define MOD 998244853
   
4. 
   
5. using namespace std;
   
6. 
   
7. int main() {
   
8.     int n, k;
   
9.     cin >> n >> k;
   
10.     n -= k;
    
11. 
    
12.     vector<int> dp(n + 1, 0);
    
13.     dp[0] = 1;
    
14. 
    
15.     for (int i = 1; i <= k; ++i) {
    
16.         for (int j = i; j <= n; ++j) {
    
17.             dp[j] = (dp[j] + dp[j - i]) % MOD;
    
18.         }
    
19.     }
    
20.    
    
21.     cout << dp[n] << endl;
    
22.     return 0;
    
23. }

复制代码

### C - sgt 维护的值看看是否冗余
你提到`sgt`（线段树）需要维护的值时，需要确认是否存在冗余。对于只需要单点修改的情况，不需要进入`up`和`dn`。

### 总结：
1. **转化思路** - 对于不容易处理的复杂限制条件，可以尝试通过不同的角度（例如横向与纵向转换）来简化问题。
2. **背包问题** - 遇到求解和或积等于某定值的问题时，可以通过背包DP的方式来解决。
3. **数据结构优化** - 在使用数据结构如线段树时，确保操作的值没有冗余，优化复杂度。对于单点修改，只需要更新相关节点，不需要进行其他多余操作。

希望这些解答能帮助你更清晰地理解和解决这些问题！如果还有其他不明白的地方，随时提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

简柠啦

sfqxx

666

harryhan123

666

很cool的阳

磷酸

闻币而来

ooio

曾热爱这世界

&#128076;

zsy0226

币

trinityee

看看

森林格格屋

谢谢