求找找问题在哪里
查看原帖
求找找问题在哪里
641246
laoyouxiaoyue楼主2023/3/14 11:06
// Problem: FAVDICE - Favorite Dice
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP1026
// Memory Limit: 1 MB
// Time Limit: 391000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ios                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define x first
#define y second
#define PII pair<int, long long>
#define int long long
#define pyes cout << "yes" << '\n';
#define pno cout << "no" << '\n';
#define pYes cout < "Yes" << '\n';
#define pNo cout << "No" << '\n';
#define endl "\n"
int a[2000][2000];
int ans[2000];
const int mod = 998244353;
unordered_map<int, int> digit;
unordered_map<int, vector<PII>> s;
vector<int> num;
int total[2000];
int l, r;
int qmi(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b /= 2;
        a = a * a % mod;
    }
    return res % mod;
}
void dfs(int index, int flag) {
    // cout<<num[index];
    // cout<<num[index]<<endl;
    if (ans[index])
        return ;
    if (index == 0) return;
    int res = 0;
    for (int k = 0; k < index; k++) {
        // cout<<num[index]<<" "<<num[k]<<endl;
        dfs(k, 0);
       //cout << k << endl;
        res=(res+ ans[k])%mod;
        //	cout<<num[index]<<" "<<num[k]<<" "<<digit[num[k]]<<" "<<total[index]-digit[num[index]]<<endl;
        for (int i = 0; i < s[num[index]].size(); i++) {
            PII s1 = s[num[index]][i];
            if (flag == 1 && (s1.first != l || s1.second != r))
                continue;
            for (int j = 0; j < s[num[k]].size(); j++) {

                PII s2 = s[num[k]][j];
              //   cout<<num[index]<<" "<<s1.first<<" "<<s1.second<<" "<<s2.first<<" "<<s2.second<<endl;
                int sb = ((s1.first - s2.first) * (s1.first - s2.first) + (s1.second - s2.second) * (s1.second - s2.second))%mod;
                res = (sb + res) % mod;
            }
        }
       
    }
    res = res * qmi(total[index] - digit[num[index]], mod - 2, mod) % mod;
    ans[index] = (ans[index] + res) % mod;
}
signed main(void) {
    int n, m;
    ios
            cin >>
        n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            s[a[i][j]].push_back({i, j});
            digit[a[i][j]]++;
            num.push_back(a[i][j]);
        }
    }
    sort(num.begin(), num.end());
    num.resize(unique(num.begin(), num.end()) - num.begin());
    sort(num.begin(), num.end());
    for (int i = 0; i < num.size(); i++) {
        if (i != 0)
            total[i] = total[i - 1] + digit[num[i]];
        else
            total[i] = digit[num[i]];
    }

    cin >> l >> r;
    int sg = a[l][r];
    int index = find(num.begin(), num.end(), sg) - num.begin();
    dfs(index, 1);
    // for(int i=0;i<num.size();i++)
    // {
    // cout<<ans[i]<<endl;
    // }
    cout << ans[index] % mod;
}
2023/3/14 11:06
加载中...