官方网站建设要点,网络优化概念,中国加盟网,国内手机app开发公司King Gym - 102471H
题意#xff1a;
给你一个数组b#xff0c;让你找到一个最长的最长的king子序列#xff0c;如果长度大于等于n/2#xff0c;输出长度值#xff0c;否则输出-1 一个序列(a1,a2,...,an)(a_{1},a_{2},...,a_{n})(a1,a2,...,an)是king序列当且仅当…King Gym - 102471H
题意
给你一个数组b让你找到一个最长的最长的king子序列如果长度大于等于n/2输出长度值否则输出-1 一个序列(a1,a2,...,an)(a_{1},a_{2},...,a_{n})(a1,a2,...,an)是king序列当且仅当存在一个整数q,1qp,对于所有的i∈[2,n],qai−1≡ai(modp)qa_{i-1}≡a_{i}(\mod p)qai−1≡ai(modp)
题解
qai−1≡ai(modp)qa_{i-1}≡a_{i}(\mod p)qai−1≡ai(modp)这个式子可以理解为在模p意义下找到一个最长的等比数列q是多少不知道 题目有个特殊性质如果长度大于等于n/2输出长度值小于输出-1。当答案超过n/2时说明有一半以上的数都参与了king子序列的组成也就说说子序列中相邻两个数在原序列中不会距离太远一定会有两个数相邻或者紧靠着 我们随机在序列最终随机取两个数这两个数出现在序列中的可能性大于1/4(1/2) * (1/2) (1/4) ) 如果我们取x次出现在答案的可能性就变成1−(34)x1-(\frac{3}{4})^x1−(43)x 只要x够大可能性就无限趋近于1 因此这个题可以这样搞我们每次随机一个位置x分别选取(x,x1)或者(x,x1)作为king子序列中的一部分然后求公比求最长子序列的长度一直更新最大长度即可
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
mt19937 rnd(time(0));
int n;
ll p;
ll poww(ll a,ll b){ll ans1;while(b){if(b1)ansans*a%p;aa*a%p;b1;}return ans%p;
}
const int maxn2e59;
ll dp[maxn];
ll a[maxn];unordered_mapll,llmp;
ll solve(int l,int r){ll res0;ll q,inv;//概率q1ll*a[r]*poww(a[l],p-2)%p;
// coutqqendl;invpoww(q,p-2);for(int i1;in;i){ll pre1ll*a[i]*inv%p;if(mp.count(pre))dp[i]mp[pre]1;else dp[i]1;mp[a[i]]max(mp[a[i]],dp[i]);resmax(res,dp[i]);}mp.clear();return res;
}
int main()
{//rd_test();int t;read(t);while(t--){scanf(%d%lld,n,p);for(int i1;in;i)read(a[i]);ll ans0;for(int i1;i25;i){int xrnd()%(n-1)1;
// printf(%d %d\n,x,x1);if(x1n)ansmax(ans,solve(x,x1));if(x2n)ansmax(ans,solve(x,x2)); }if(ans*2n)printf(-1\n);else printf(%lld\n,ans);}//Time_test();
}
