[心之碎片] - 20240817模拟赛

柿子饼同学

总结与反思

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

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

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

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

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

f[0] = 1;
    cin >> n >> k;
    n -= k;

    for (int i = 1; i <= k; i++) {
        for (int j = i; j <= n; j++) {
            f[j] = (f[j] + f[j - i]) % P;
        }
    }

    cout << f[n];

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

#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[N][N];
int n, m, K;
ll p[N], f[N][N][30];
long long same, all;
pii g[N][N][30];
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[i];
    }

    int lim = log2(K);
    p[0] = B;
    for(int i = 1; i <= lim; i++){
        p[i] = p[i - 1]*p[i - 1];
    }

    for(int d = 0; d < 8; d++){
        // 录入 f, g
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                f[i][j][0] = s[i][j];
                g[i][j][0] = make_pair((i + dx[d] + n) % n, (j + dy[d] + 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[i][j][k - 1].first;
                    int y = g[i][j][k - 1].second;

                    f[i][j][k] = f[i][j][k - 1]*p[k] + f[x][y][k - 1];
                    g[i][j][k] = g[x][y][k - 1];
                }
            }
        }

        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[k] + f[cur.first][cur.second][k];
                        cur = g[cur.first][cur.second][k];
                    }
                }

                cnt[hash]++;
            }
        }
    }

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

FishC

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

### 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[0] = 1;

    for (int i = 1; i <= k; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] = (dp[j] + dp[j - i]) % MOD;
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}

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

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

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

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

简柠啦

sfqxx

666

harryhan123

666

很cool的阳

磷酸

闻币而来

ooio

曾热爱这世界

👌

zsy0226

币

trinityee

看看

森林格格屋

谢谢