Magical Array

Created by LXC on Tue Aug 1 20:23:54 2023

https://codeforces.com/problemset/problem/1704/D

ranting: 1900

tag: constructive algorithms, hashing, implementation, math

problem

有一个长度为m的隐藏数组b。b的每个元素值都不知道。

我们利用b数组的生成了n个数组$c_1, c_2, \cdots , c_n$，其中一个数组$c_k$的生成方式不一样

数组$c_t, 1\le t\le n$生成的过程如下：

首先让$c_t = b$。然后对其操作至少一次。

对于$t \ne k$，我们每次操作可以选择$2\le i < j \le m-1$，让$c_{t,i}$和$c_{t,j}$减少1，让$c_{t,i-1}$和$c_{t,j+1}$增加1。记为操作1。

对于$t = k$，我们每次操作可以选择$2\le i < j \le m-2$，让$c_{t,i}$和$c_{t,j}$减少1，让$c_{t,i-1}$和$c_{t,j+2}$增加1。记为操作2。

求k，以及对$c_k$操作了多少次。

$3 \leq n \leq 10^5, 7 \leq m \leq 3 \cdot 10^5$

solution

定义$f(c_t) = \sum \limits_{i=1}^{n} c_{t, i}\times i$

操作1并不会影响f值，

$a_{i-1} \times (i-1) + a_i \times i + a_j \times j + a_{j+1} \times (j+1) = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}) -a_{i-1} + a_{j+1}$

$(a_{i-1}+1) \times (i-1) + (a_i-1) \times i + (a_j-1) \times j + (a_{j+1}+1) \times (j+1) = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}) -a_{i-1} + a_{j+1}$

而操作2每执行一次会让f增大1。

$a_{i-1} \times (i-1) + a_i \times i + a_j \times j + a_{j+1} \times (j+1) +a_{j+2} \times (j+2) = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}+a_{j+2}) -a_{i-1} + a_{j+1}+2 \times a_{j+2}$

$(a_{i-1}+1) \times (i-1) + (a_i-1) \times i + (a_j-1) \times j + a_{j+1} \times (j+1) + (a_{j+2}+1) \times (j+2) = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}+a_{j+2}) -a_{i-1} + a_{j+1}+ 2 \times a_{j+2} +1$

所以$f(c_k)$不同于其他$f_{c_i}$，容易找到$k$，且操作的次数为$f(c_k)-f(c_i)$

注意$f(c_i)$会溢出，但是$f(c_k)-f(c_i)$却没有溢出。因此即便溢出了得到的答案也是正确的，

或者模一个大数也正确。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

#define mint Modint<MOD>
template <const int _MOD>
struct Modint {
    int v;
    Modint() { v = 0; }
    Modint(long long o) { v = o % _MOD; }
    int val() { return v; }
    int pow(long long o) {
        int ret = 1, tmp = v;
        while (o) {
            if (o & 1)
                ret = ((long long)ret * tmp) % _MOD;
            o >>= 1;
            tmp = ((long long)tmp * tmp) % _MOD;
        }
        return ret;
    }
    void operator=(long long o) { v = o % _MOD; }
    bool operator==(long long o) const { return v == o; }
    bool operator==(Modint o) const { return v == o.v; }
    bool operator!=(long long o) const { return v != o; }
    bool operator!=(Modint o) const { return v != o.v; }
    bool operator<(long long o) const { return v < o; }
    bool operator<(Modint o) const { return v < o.v; }
    bool operator>(long long o) const { return v > o; }
    bool operator>(Modint o) const { return v > o.v; }
    bool operator<=(long long o) const { return v <= o; }
    bool operator<=(Modint o) const { return v <= o.v; }
    bool operator>=(long long o) const { return v >= o; }
    bool operator>=(Modint o) const { return v >= o.v; }

    Modint operator+(long long o) const { return *this + Modint(o); }
    Modint operator+(Modint o) const { return ((long long)v + o.v) % _MOD; }
    Modint operator*(long long o) const { return *this * Modint(o); }
    Modint operator*(Modint o) const { return (long long)v * o.v % _MOD; }

    Modint operator-(long long o) const { return *this - Modint(o); }
    Modint operator-(Modint o) const {
        return ((long long)v - o.v + _MOD) % _MOD;
    }

    Modint operator/(long long o) const { return *this / Modint(o); }
    Modint operator/(Modint o) const {
        return ((long long)v * o.pow(_MOD - 2)) % _MOD;
    }
    void operator+=(long long o) { *this = *this + o; }
    void operator+=(Modint o) { *this = *this + o; }
    void operator*=(long long o) { *this = *this * o; }
    void operator*=(Modint o) { *this = *this * o; }
    void operator-=(long long o) { *this = *this - o; }
    void operator-=(Modint o) { *this = *this - o; }
    void operator/=(long long o) { *this = *this / o; }
    void operator/=(Modint o) { *this = *this / o; }

    Modint operator^(long long o) { return Modint(pow(o)); }
    Modint operator^(Modint o) { return Modint(pow(o.v)); }

    template <class T>
    friend bool operator==(T o, Modint u) {
        return u == o;
    }
    template <class T>
    friend Modint operator+(T o, Modint u) {
        return u + o;
    }
    template <class T>
    friend Modint operator*(T o, Modint u) {
        return u * o;
    }
    template <class T>
    friend Modint operator-(T o, Modint u) {
        return Modint(o) - u;
    }
    template <class T>
    friend Modint operator/(T o, Modint u) {
        return Modint(o) / u;
    }

    void operator++() { *this = *this + 1; }
    void operator--() { *this = *this - 1; }
    void operator++(int k) { *this = *this + 1; }
    void operator--(int k) { *this = *this - 1; }

    template <const int T>
    friend std::istream& operator>>(std::istream& in, Modint<T>& modint) {
        ll x;
        in >> x;
        modint = Modint<T>(x);
        return in;
    }

    template <const int T>
    friend std::ostream& operator<<(std::ostream& os, const Modint<T>& modint) {
        os << modint.v;
        return os;
    }
};

void sol() {
    int n, m;
    cin >> n >> m;
    vector<vector<mint>> c(n, vector<mint>(m, 0));
    vector<mint> h(n);
    for (auto& i : c) {
        for (auto& j : i) {
            cin >> j;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            h[i] += j * c[i][j];
        }
    }
    if (count(h.begin(), h.end(), h[0]) == 1) {
        cout << "1 " << h[0] - h[1] << "\n";
    } else {
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (h[i] != h[0])
                p = i;
        }
        cout << p + 1 << " " << h[p] - h[0] << "\n";
    }
}

void sol2() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> c(n, vector<ll>(m, 0));
    vector<ll> h(n);
    for (auto& i : c) {
        for (auto& j : i) {
            cin >> j;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            h[i] += j * c[i][j];
        }
    }
    if (count(h.begin(), h.end(), h[0]) == 1) {
        cout << "1 " << h[0] - h[1] << "\n";
    } else {
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (h[i] != h[0])
                p = i;
        }
        cout << p + 1 << " " << h[p] - h[0] << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}