正題

題目鏈接:https://www.luogu.com.cn/problem/U138580

---

題目大意

兩個長度為$n$的序列，要求重排后同位置的相加后眾數的個數最多。

---

解題思路

定義$a_i$為第一個序列中$i$的出現次數，那么同理有$b$
不難對于每個眾數$i$的出現次數$c_i$，那么有$$c_n=\sum _{i=1}^{n?1}min\{a_i,b_{n?i}\}$$

發現這個東西很難處理，但是如果每個$a_i,b_i$都是$1$那么同化為卷積可以用$NTT$進行計算了。

所以我們可以對于每個$z$分開計算也就是$$c_n=\sum _{i=1}^{n?1}(a_i\ge z)?(b_{n?i}\ge z)$$

但是這樣$z$的個數非常之多，但是當$z$很大時這個序列會變的很稀疏，那么我們定義一個值$T$，當$z>T$時我們就用暴力處理即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long using namespace std; const ll N=3e5+10,T=10,XJQ=998244353; ll n,m,lg,invn,maxs,ans[N],a[N],b[N]; ll g[N],gi[N],r[N],x[N],y[N]; vector<ll > pa,pb; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } void NTT(ll *f,ll op){for(ll i=1;i<n;i++)if(r[i]<i)swap(f[i],f[r[i]]);for(ll p=2;p<=n;p<<=1){ll len=p>>1,tmp=g[p];if(op==-1)tmp=gi[p];for(ll k=0;k<n;k+=p){ll buf=1;for(ll i=k;i<k+len;i++){ll tt=buf*f[i+len]%XJQ;f[i+len]=(f[i]-tt+XJQ)%XJQ;f[i]=(f[i]+tt)%XJQ;buf=buf*tmp%XJQ;}}}if(op==-1)for(ll i=1;i<=n;i++)f[i]=f[i]*invn%XJQ;return; } void solve(ll k){for(ll i=0;i<n;i++)x[i]=(a[i]>=k);for(ll i=0;i<n;i++)y[i]=(b[i]>=k);NTT(x,1);NTT(y,1);for(ll i=0;i<n;i++)x[i]=x[i]*y[i]%XJQ;NTT(x,-1);for(ll i=0;i<n;i++)ans[i]+=x[i];return; } int main() {scanf("%lld",&m);for(n=1;n<=2e5;n<<=1)lg++;invn=power(n,XJQ-2);for(ll i=2;i<=n;i<<=1)g[i]=power(3,(XJQ-1)/i),gi[i]=power(g[i],XJQ-2);for(ll i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));for(ll i=1;i<=m;i++){ll x;scanf("%lld",&x);a[x]++;}for(ll i=1;i<=m;i++){ll x;scanf("%lld",&x);b[x]++;}for(ll i=1;i<=T;i++)solve(i);for(ll i=1;i<=1e5;i++)if(a[i]>T)pa.push_back(i);for(ll i=1;i<=1e5;i++)if(b[i]>T)pb.push_back(i);for(ll i=0;i<pa.size();i++)for(ll j=0;j<pb.size();j++)ans[pa[i]+pb[j]]+=min(a[pa[i]],b[pb[j]])-T;for(ll i=0;i<=n;i++) maxs=max(maxs,ans[i]);printf("%lld",maxs);return 0; }

總結

以上是生活随笔為你收集整理的[2020.11.4NOIP模拟赛]简单的打击【NTT】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。