Geometric Progression - 每天一把CF - 20201029

2020-10-29

dp

567C 1700

题目

原题链接:https://codeforces.com/problemset/problem/567/C

思路

题目大意：给定n个数，问着n个数中有多少个以k为公比长度为3的子序列。

思路：

这道题的思路来自于之前做过的一道题 CF1426F 。其中的精髓都是去记录在这个状态前出现的前一个状态的次数。

然后此题注意特殊处理一下数组中的0以及k=1这两种情况.

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;#define mes0(c) memset((c),0,sizeof(c))
#define fsios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define fi first
#define se secondconst ll MAX = 2e5 + 5;
const ll ifi = 1e15;ll n, k, tp, zero;
ll ans;
map<ll, ll> mp, cnt;int main() {
    fsios;while (cin >> n >> k) {
    mp.clear();ans = zero = 0;if (k == 1) {
    for (int i = 1; i <= n; i++) {
    cin >> tp;if (mp.count(tp))mp[tp]++;elsemp.emplace(make_pair(tp, 1));}for (auto it = mp.begin(); it != mp.end(); it++) {
    tp = it->se;ans += (tp * (tp - 1) * (tp - 2)) / 6;}}else {
    for (int i = 1; i <= n; i++) {
    cin >> tp;if (mp.count(tp))mp[tp]++;elsemp.emplace(make_pair(tp, 1));if (tp % k == 0 && tp != 0)cnt[tp * k] += mp[tp / k];else if (tp == 0) zero++;ans += cnt[tp];}ans += zero * (zero - 1) * (zero - 2) / 6;}cout << ans << endl;}return 0;
}