牛客练习赛42 出题的诀窍（数学+hash）

出题的诀窍

题目链接：https://ac.nowcoder.com/acm/contest/393/C

题解：

由于他是在每一行选取一个元素，然后纵向来比较，这里行的顺序是不会影响的，所以我们将每一个数存入哈希表中，然后对每一个数来进行考虑。

第一行的数，对答案的贡献为m，而第二行对答案的贡献为m*(m-1)...以此类推。

这里注意对同一行有多个相同元素的情况考虑一下。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int  N = , M = , MOD = 1e9 + ;

ll a[N][N], pm[N];

int n, m;

struct Edge {

    ll v, next, i;

} e[N * N];

ll head[M], tot, h[M];

ll f[N * N], d[N * N];

void adde(ll u, ll v, ll i) {

    e[tot].i = i;

    e[tot].v = v;

    e[tot].next = head[u];

    head[u] = tot++;

}

void hsh(ll x, ll y) {

    ll now = x % M;

    while(h[now] != - && h[now] != x) {

        now += ;

        if(now >= M)

            now -= M;

    }

    h[now] = x;

    adde(now, x, y);

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie();

    cin >> m >> n;

    memset(head, -, sizeof(head));

    memset(h, -, sizeof(h));

    pm[] = ;

    for(int i = ; i <= n; i++)

        pm[i] = pm[i - ] * m % MOD;

    for(int i = ; i <= n; i++) {

        for(int j = ; j <= m; j++) {

            cin >> a[i][j];

            hsh(a[i][j], i);

        }

    }

    ll ans = , cnt, num, pr;

    for(int x = ; x < M; x++) {

        if(h[x] != -) {

            pr = ;

            cnt = ;

            num = ;

            for(int i = head[x]; i != -; i = e[i].next) {

                d[++cnt] = e[i].i;

            }

            for(int i = ; i <= cnt; i++) {

                if(i ==  || d[i] != d[i - ])

                    f[++num] = ;

                else

                    f[num]++;

            }

            for(int i = ; i <= num; i++) {

                ans += pm[n - i] * pr % MOD * f[i] % MOD * h[x] % MOD;

                pr = pr * (m - f[i]) % MOD;

                ans %= MOD;

            }

        }

    }

    cout << ans;

    return ;

}