算法|2019西安EC-final H-king （随机化+dp） dp|#

2019西安EC-final H-king （随机化+dp）

题目链接

题面
随机化算法

正确性
复杂度

check
AC代码
总结

题目链接题面给出一个长度为n的序列，和一个小于1e9+7的质数。如果最长的模意义下的等比数列长度小于n/2则输出-1，否则则输出长度。
随机化算法因为小于n/2的时候不用求出长度，而当长度大于n/2时，我们可以通过相邻两个数或者隔着一个数来计算q（通过逆元），再通过q出现的频率去判断是否可能为q，所以可以采取随机化算法。
正确性
相邻时的最坏情况是隔着取的（比如 1 3 2 5 4 7 8）此时取不到正确的q，但此时是隔着一个数的最好情况（会取到3次q）。
隔着一个取的最坏情况是相邻着的（比如 1 2 4 8 16）此时取不到正确的q，但此时是相邻取的最好情况（会取到4次q）。
而综合起来的最坏情况就是隔着两个出现下一个（比如 1 3 5 2 7 11 4 8），此时为最坏情况q只出现1次，n为8，所以可以以8/n作为分界线。
复杂度
因为两次取得的q约有2*n个因为以n/8为分界线，所以最多有16个q，遍历check为O（N），则总复杂度约为O（N）带一个不大的常数。所以可行。
check 当得到q后遍历并用unordered_map来dp求得长度。
AC代码

#include using namespace std; typedef long long ll; const int maxn = 2e5 + 5; int T; int n; ll p; ll a[maxn]; vector q; ll ksm(ll a, ll n) { a %= p; ll res = 1; while (n) { if (n & 1) res = res * a % p; a = a * a % p; n >>= 1; } return res; } void getq() { q.clear(); for (int i = 0; i < n - 1; i++) { q.push_back(a[i + 1] * ksm(a[i], p - 2) % p); } for (int i = 0; i < n - 2; i++) { q.push_back(a[i + 2] * ksm(a[i], p - 2) % p); } unordered_map mp; for (int i = 0; i < q.size(); i++) { mp[q[i]]++; } q.clear(); for (auto it : mp) { if (it.second >= n / 8) q.push_back(it.first); } return; }int check(ll q) { unordered_map dp; int ret = 0; if (q == 1) { for (int i = n - 1; i >= 0; i--) { dp[a[i]]++; ret = max(dp[a[i]], ret); } return ret; } for (int i = n - 1; i >= 0; i--) { dp[a[i]] = 1; dp[a[i]] = max(dp[a[i] * q % p] + 1, dp[a[i]]); ret = max(ret, dp[a[i]]); } return ret; } int main() { srand(time(0)); scanf("%d", &T); while (T--) {scanf("%d %lld", &n, &p); for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); }getq(); int ans = 0; for (auto it : q) { ans = max(ans, check(it)); } if (ans * 2 < n) cout << -1 << endl; else cout << ans << endl; }return 0; }

总结 【算法|2019西安EC-final H-king （随机化+dp）】场上没有想出这道题，也没有想到随机化算法。还需要努力。