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

Solost

2023 年 01 月 19 日

363 次浏览

暂无评论

1455字数

题目题解

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

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/1665745202.png)

# 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.第二次尝试，我们换个思路，ai*aj没办法压缩（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

```C++
#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;
}
```

最后修改：2023 年 02 月 02 日