2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers

solution

我们先来分析一下，我们需要寻找三个数，然后满足一定的条件，由于n=5000,n的三次方的复杂度肯定是不可取的，我们就得想办法优化常数。

1.第一次的错误尝试，使用vector<pair<int, pair<int, int>>>，第一维度存放a[i] a[j] % mod，第二维度存放i,j,然后再枚举a[i]，用f[(a[i] a[j] % mod + a[i] % mod) % mod]++,来存放5000以内的i等于时的答案，最后再将f[i]减去（a[i] a[j] + a[i]和a[i] a[j] + a[j])这种情况。我们可以看出，这个方法基本和暴力没啥区别，属于脱裤子放屁了。

2.第二次尝试，我们换个思路，aiaj没办法压缩（ps.刚开始没想到压缩这个），我们就压缩a[i],我们将a[i] % mod，存放到b[i]里面，计算a[i] % mod后相同的数目，最后再将(a[i] a[j] % mod + i % mod) % mod的数目计算出来就可以了，再减去a[i] a[j] + a[i]和a[i] a[j] + a[j])这种情况。这种情况优化了一部分，但是优化程度还是不够，如果a[i] % mod，但是mod ==5000 == n那就相当于没有优化。于是我们将矛头转向优化a[i] a[j]

3.于是有了解法三，我们将b[a[i] * a[j] % mod]的数目先算出来，然后枚举f[a[i] % mod + j % mod]，i属于1-n，j属于0-p -1，这样我们就可以得到答案了。

show code

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
ll a[N], f[5100], b[5100];//由于b里面存储的是次数，因此有可能会爆int，所以顺便存成ll
void solve(){
    int n, p;
    cin >> n >> p;
    int mod = p;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            b[(1ll * a[i] * a[j]) % mod]++;
            ll t1 = ((1ll * a[i] * a[j]) % mod + a[i] % mod) % mod;
            ll t2 = ((1ll * a[i] * a[j]) % mod + a[j] % mod) % mod;//减去有两个数相同的情况
            f[t1]--;
            f[t2]--;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < p; j++){
            int t = (a[i] % mod + j % mod) % mod;
            f[t] += b[j];
        }
    }
    for(int i = 0; i < p; i++){
        cout << f[i] * 2 << " ";//因为三元组前两个数交换无所谓，所以×2，我们计算的时候不会算i,j和j,i只会算一遍
    }
    cout << endl;
}
int main(){
    // IOS;
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}