列表

详情

NC221009. 同源数组(EasyVersion)

描述

本题有Easy,Hard两个版本，两个版本之间的区别仅在数据范围，通过Hard Version的代码可以直接通过Easy Version。保证Easy Version的测试用例集是Hard Version的子集

智乃酱最近学习了前缀和、差分。她现在对于这两个操作产生了浓厚的兴趣。

具体来说，前缀和是这样一种操作，假设数组是数组的前缀和数组，则有

而差分的操作则是前缀和反过来，假设数组是数组的差分数组，则有

我们将先求出数组，再把中的值赋值回称为对数组做一次前缀和，同理，将先求出数组，再把中的值赋值回数组称之为一次差分。

如果两个长度相同的数组可以通过对数组或者数组做若干次前缀和或者差分，使两个数组中所有元素在mod (p是一个素数)下是相等的，则称两个数组同源。
显然易得，如果存在三个长度相同的数组，如果同源且同源，则也是同源的。

我们把一些两两之间互相同源的数组放到一起，它们就称为一个“同源集合”。

现在给你n个长度大小均为m的数组，你需要将它们划分成若干个同源集合，要求你划分的集合数目最少。
请输出一个合理的划分方案。

输入描述

第一行输入三个正整数。
接下来n行，每行m个整数表示第i个数组的第j个元素
Easy Version 额外限制，保证p=998244353。

输出描述

本题为spj，你可以输出任何符合题目要求的答案。
首先输出一个正整数g表示划分的同源集合数目。
接下来按照顺序输出每个集合中的数组编号。（数组从0开始编号）
输出行，首先输出一个整数，表示集合的大小，接下来输出一行若干整数，整数与整数之间空一个空格。

示例1

输入: 

15 5 998244353
0 0 0 0 5
1 1 1 1 1
0 0 1 1 1
1 3 6 10 15
0 0 0 7 7
1 0 0 0 0
0 0 0 0 6
0 0 0 7 10
0 0 0 9 8
1 2 1 2 1
0 0 0 0 5
0 0 1 2 1
1 2 3 4 5
0 0 0 9 2
0 0 0 7 10086

输出: 

8
4
5 1 12 3
1
9
1
2
1
11
3
4 7 14
2
13 8
2
0 10
1
6

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 734ms, 内存消耗: 1228K, 提交时间: 2021-10-15 20:30:12 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL mod;
LL power(LL a, LL r) {
    LL res = 1;
    for (; r; r >>= 1, a = a * a % mod)
        if (r & 1) res = res * a % mod;
    return res;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m >> mod;
    map<vector<LL>, vector<int>> mp;
    for (int i = 0; i < n; i += 1) {
        vector<LL> a(m);
        for (LL& x : a) cin >> x;
        int s = 0;
        while (s < m and a[s] == 0) s += 1;
        if (s + 1 < m) {
            LL k = (mod - a[s + 1]) * power(a[s], mod - 2) % mod;
            vector<LL> ks(m);
            ks[0] = 1;
            for (int i = 0; i + 1 < m; i += 1) ks[i + 1] = ks[i] * (k + i) % mod * power(i + 1, mod - 2) % mod;
            for (int i = m - 1; i > s; i -= 1)
                for (int j = s; j < i; j += 1)
                a[i] = (a[i] + a[j] * ks[i - j]) % mod;
        }
        mp[a].push_back(i);
        //for (LL x : a) cout << x << " "; cout << "\n";
    }
    cout << mp.size() << "\n";
    for (const auto& [_, v] : mp) {
        cout << v.size() << "\n";
        for (int x : v) cout << x << " ";
        cout << "\n";
    }
}

上一题

© 2024 nowcoder.com