Preface
这两天才发现原来百度之星的题目已经公开了，既然没事干就补一下现场打的这场吧
这场最大的问题就是没有看榜选择正序开题，导致在B题上花了很长时间还没过，导致去写后面的题的时候已经过了一个多小时了
虽然最后在签完后面的题后回来想出了B的很多Corner Case把这道过的人最少的题写了，但后面剩的时间实在是太少了
最后看了眼H发现是个傻逼题，然后发现比赛的时候没带纸质模板NTT写不来了，直接弃疗交卷走人
后面经典因为罚时和省金失之交臂，不过如果带个板子多写一题可能结果也不一样了，到时候可能还得报名打下第三场的说
A. 星际航行
枚举最后在哪一维上会合，不难发现其它两维都是变成中位数是最优的，可以先统计这部分的答案
然后对剩下的一维，如果以起始位置的坐标\(t\)作距离函数，不难发现这个函数具有单峰性，可以三分起始坐标然后模拟算答案即可
总复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=100005,LIM=2e6;
int n,x[N],y[N],z[N],dx[N],dy[N],dz[N]; LL resx,resy,resz,ans=1e18;
inline LL calc(CI st,int *a,LL ret=0)
{
for (RI i=1;i<=n;++i) ret+=abs(a[i]-(st+i-1)); return ret;
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i)
scanf("%d%d%d",&x[i],&y[i],&z[i]);
sort(x+1,x+n+1); sort(y+1,y+n+1); sort(z+1,z+n+1);
for (i=1;i<=n;++i) resx+=abs(x[i]-x[n+1>>1]);
for (i=1;i<=n;++i) resy+=abs(y[i]-y[n+1>>1]);
for (i=1;i<=n;++i) resz+=abs(z[i]-z[n+1>>1]);
int l,r,lmid,rmid;
l=-LIM; r=LIM; while (r-l>2)
{
lmid=l+(r-l)/3; rmid=r-(r-l)/3;
if (calc(lmid,x)<=calc(rmid,x)) r=rmid; else l=lmid;
}
for (i=l;i<=r;++i) ans=min(ans,calc(i,x)+resy+resz);
l=-LIM; r=LIM; while (r-l>2)
{
lmid=l+(r-l)/3; rmid=r-(r-l)/3;
if (calc(lmid,y)<=calc(rmid,y)) r=rmid; else l=lmid;
}
for (i=l;i<=r;++i) ans=min(ans,calc(i,y)+resx+resz);
l=-LIM; r=LIM; while (r-l>2)
{
lmid=l+(r-l)/3; rmid=r-(r-l)/3;
if (calc(lmid,z)<=calc(rmid,z)) r=rmid; else l=lmid;
}
for (i=l;i<=r;++i) ans=min(ans,calc(i,z)+resx+resy);
return printf("%lld",ans),0;
}
B. 小度的规划
这题的思路说实话不难想，但就是很多细节和特殊情况容易写挂
由于数据范围不大，不妨先枚举确定\(X\)，同时记A,B走到\(X\)所需的时间为\(t_A,t_B\)，则先决条件为\(t_A\ge t_B\)
不妨先假设A,B同时到达\(X\)，而多出的\(t_A-t_B\)次操作可以贪心地留在后面用，这样只要把\(A\to X\)这条路径上都先放上一个金币即可
然后考虑从\(X\)往外走，贪心地把之前剩下的操作优先铺放在靠前的点上，不难发现这样一定是最优的
大致思路就是这样，但由于这道题两人的行动逻辑的问题，有各种极其隐蔽的坑点需要注意，比如当\(X\)和A,B的初始位置重合时坑了我好久
具体细节看代码吧，复杂度\(O(n^2)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=1505;
int n,x,y,c[N],a[N],pa,pb,disa[N],disb[N],pre[N],ans; vector <int> v[N];
inline void DFS1(CI now,int *dis,CI fa=0)
{
for (int to:v[now]) if (to!=fa) dis[to]=dis[now]+1,DFS1(to,dis,now);
}
inline void travel(CI st,CI tar,CI now,CI fa=0)
{
if (now==tar)
{
for (int x=tar;x!=st;x=pre[x]) ++a[x]; return;
}
for (int to:v[now]) if (to!=fa) pre[to]=now,travel(st,tar,to,now);
}
inline void DFS2(CI now,int left,CI st,CI fa=0,int pre=0)
{
if (c[now]==0) return; if (now!=st) ++a[now]; a[now]=min(a[now],c[now]);
int tmp=min(c[now]-a[now],left); pre+=tmp+a[now]; left-=tmp; ans=max(ans,pre);
for (int to:v[now]) if (to!=fa) DFS2(to,left,st,now,pre);
}
int main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;++i) scanf("%d",&c[i]);
scanf("%d%d",&pa,&pb); DFS1(pa,disa); DFS1(pb,disb);
for (i=1;i<=n;++i) if (disa[i]>=disb[i])
{
memset(a,0,sizeof(a)); travel(pb,i,pb);
if (i==pa&&i==pb) ++a[i]; DFS2(i,disa[i]-disb[i],i);
}
return printf("%d",ans),0;
}
C. 夏日漫步
签到题，直接BFS即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=200005,M=1e6+5;
int n,a[N],pre[M],dis[N],vis[N]; vector <int> v[N];
inline int BFS(CI st,CI tar)
{
queue <int> q; dis[st]=0; vis[st]=1; q.push(st);
while (!q.empty())
{
int now=q.front(); q.pop();
for (int to:v[now]) if (!vis[to]) vis[to]=1,dis[to]=dis[now]+1,q.push(to);
}
return dis[tar];
}
int main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i)
{
if (scanf("%d",&a[i]),pre[a[i]]) v[pre[a[i]]].push_back(i); pre[a[i]]=i;
}
for (i=1;i<n;++i) v[i].push_back(i+1),v[i+1].push_back(i);
return printf("%d",BFS(1,n)),0;
}
D. 怪兽
这题大力出奇迹，要么写\(O(p)\)的做法要么写\(O(n^2)\)的做法，虽然理论上界都是\(10^8\)的但好像都能过
我的做法就是直接枚举怪兽王脚的个数，然后发现此时另外两种怪兽的信息就是一个二元二次方程组，解下方程并看解是否合法即可
实测跑的巨快无比，有可能是数据出水了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
int p,q,n1,n2,n3,mi=-1,mx=-1;
int main()
{
//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
RI i; scanf("%d%d%d%d%d",&p,&q,&n1,&n2,&n3);
for (i=0;i<=p;++i)
{
int pp=p-i,qq=q-i*n3; if (qq<0) break;
if (qq<1LL*n1*pp) break;
if (qq>1LL*n2*pp) continue;
if (n1==n2)
{
if (n1*pp==qq) { mi=i; break; }
} else
{
if ((qq-n1*pp)%(n2-n1)) continue;
int y=(qq-n1*pp)/(n2-n1),x=pp-y;
if (n1*x+n2*y==qq) { mi=i; break; }
}
}
for (i=q/n3;i>=0;--i)
{
int pp=p-i,qq=q-i*n3;
if (qq<1LL*n1*pp) continue;
if (qq>1LL*n2*pp) break;
if (n1==n2)
{
if (n1*pp==qq) { mx=i; break; }
} else
{
if ((qq-n1*pp)%(n2-n1)) continue;
int y=(qq-n1*pp)/(n2-n1),x=pp-y;
if (n1*x+n2*y==qq) { mx=i; break; }
}
}
if (!~mi) return puts("-1"),0;
return printf("%d %d",mi,mx),0;
}
E. 循环同构
比赛的时候看到字符串就自动降智不想做了，因为一般现在遇到字符串都是归徐神写的
后面看官方题解讲的是SAM做法一点不会，但听包大爷说zzh是用Hash写的，遂去尝试了一手最后大力卡常卡过
其实这种暴力思路之前我一轮的时候有道题就是这样搞过去的，就是由于总串长\(S=\sum|s_i|=2\times 10^5\)，那么不同长度的串的种类数其实是\(O(\sqrt S)\)级别的
换句话说我们直接对于询问串，枚举每个位置作为开头，然后再枚举之前出现过的长度，再提出这一段Hash比较即可
关于循环同构的话就直接对每个串枚举起始位置重新算一遍Hash值即可，不难发现总数也是\(O(S)\)的
但是这里最大的问题就是如果用map/unordered_map来查询的话就会超时，所以需要手写个Hash表
总复杂度\(O(S\sqrt S)\)，极限数据跑800+ms，如果把双Hash改成单自然溢出会快一些
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
int x,y;
inline Hasher(CI X=0,CI Y=0)
{
x=X; y=Y;
}
inline LL val(void)
{
return ((1LL*x)<<31LL)|(1LL*y);
}
friend inline bool operator == (const Hasher& A,const Hasher& B)
{
return A.x==B.x&&A.y==B.y;
}
friend inline Hasher operator + (const Hasher& A,const Hasher& B)
{
return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
}
friend inline Hasher operator - (const Hasher& A,const Hasher& B)
{
return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
}
friend inline Hasher operator * (const Hasher& A,const Hasher& B)
{
return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
}
}h[N],pw[N]; int n,q; char s[N]; set <LL> rst; set <int> len;
const Hasher seed=Hasher(31,131);
inline Hasher get(Hasher *h,CI l,CI r)
{
return h[r]-h[l-1]*pw[r-l+1];
}
const int M=19260817;
struct Hash_Table
{
vector <array <LL,3>> v[M];
inline void insert(CI len,const LL& x)
{
int y=x%M; for (auto& [key,l,c]:v[y]) if (key==x&&len==l) return (void)(++c);
v[y].push_back({x,len,1});
}
inline int query(CI len,const LL& x)
{
int y=x%M; for (auto [key,l,c]:v[y]) if (key==x&&len==l) return c; return 0;
}
}c;
int main()
{
//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&q),pw[0]=Hasher(1,1),i=1;i<=200000;++i) pw[i]=pw[i-1]*seed;
for (i=1;i<=n;++i)
{
scanf("%s",s+1); int m=strlen(s+1); len.insert(m);
for (j=1;j<=m;++j) h[j]=h[j-1]*seed+Hasher(s[j]-'a',s[j]-'a');
for (rst.clear(),j=1;j<=m;++j) rst.insert((get(h,j,m)*pw[j-1]+get(h,1,j-1)).val());
for (auto x:rst) c.insert(m,x);
}
for (i=1;i<=q;++i)
{
scanf("%s",s+1); int m=strlen(s+1); LL ans=0;
for (j=1;j<=m;++j) h[j]=h[j-1]*seed+Hasher(s[j]-'a',s[j]-'a');
for (j=1;j<=m;++j) for (auto x:len)
{
if (j+x-1>m) break; ans+=c.query(x,get(h,j,j+x-1).val());
}
printf("%lld\n",ans);
}
return 0;
}
F. 跑步
妈的这题比赛的时候傻逼了，把一个前缀和就能解决的东西用主席树实现了，虽然写的也不慢但就是很难受
考虑先处理掉多个初始位置相同的情况后，枚举某个位置的猫钦定其为最后合并后的组
不难发现所有初始位置在它左边并且速度大于它的组最后都会和它合并，我们要做的就是统计这些组的个数
很容易想到用单调栈维护出每个组左边第一个速度小于等于它的组，则答案就是一段区间和的形式
比赛的时候脑抽了以为中间还有速度小于等于它的数，就写了个主席树区间查询，鉴定为纯纯的弱智
（以下代码仅用于敲响警钟，实际上只要把主席树部分改成前缀和即可）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=100005;
int n,p,x,a[N],v[N],ans,rst[N],cnt,stk[N],top,rt[N]; map <int,int> ct,mv;
class Segment_Tree
{
private:
struct segment
{
int ch[2],sum;
}node[N*40]; int tot;
public:
#define lc(x) node[x].ch[0]
#define rc(x) node[x].ch[1]
#define S(x) node[x].sum
#define TN CI l=1,CI r=cnt
#define LS l,mid
#define RS mid+1,r
inline void modify(int& now,CI lst,CI pos,CI mv,TN)
{
node[now=++tot]=node[lst]; S(now)+=mv; if (l==r) return; int mid=l+r>>1;
if (pos<=mid) modify(lc(now),lc(lst),pos,mv,LS); else modify(rc(now),rc(lst),pos,mv,RS);
}
inline int query(CI x,CI y,CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return S(y)-S(x); int mid=l+r>>1,ret=0;
if (beg<=mid) ret+=query(lc(x),lc(y),beg,end,LS);
if (end>mid) ret+=query(rc(x),rc(y),beg,end,RS); return ret;
}
#undef lc
#undef rc
#undef S
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i)
{
scanf("%d%d",&p,&x); ++ct[p];
if (ct[p]==1) mv[p]=x; else mv[p]=min(mv[p],x);
}
n=0; for (auto [x,y]:ct) a[++n]=y,v[n]=mv[x];
for (i=1;i<=n;++i) rst[++cnt]=v[i];
sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
for (i=1;i<=n;++i) v[i]=lower_bound(rst+1,rst+cnt+1,v[i])-rst;
//for (i=1;i<=n;++i) printf("%d %d\n",a[i],v[i]);
for (stk[top=0]=0,i=1;i<=n;++i)
{
while (top&&v[stk[top]]>v[i]) --top; ans=max(ans,a[i]);
if (stk[top]+1<=i-1) ans=max(ans,SEG.query(rt[stk[top]],rt[i-1],v[i]+1,cnt)+a[i]);
stk[++top]=i; SEG.modify(rt[i],rt[i-1],v[i],a[i]);
}
return printf("%d",ans),0;
}
G. 红色括号
个人感觉这场最难的一题，感觉有学到了关于括号序列的有用的trick
首先发现最后不匹配的括号一定形如))))(((，即由若干个右括号开头，再跟上若干个左括号
为了方便统计我们可以分别计算，比如只算出未匹配的右括号个数，然后根据经典trick把序列翻转并把括号取反后再做一遍即可得到未匹配的左括号个数了
还是熟悉地把(看成\(1\)，)看成\(-1\)，则不难发现所有未匹配的位置一定是严格的前缀最小值点，即若\(i\)为一个未匹配的右括号，则\(\forall j\in[1,i),pfx_j>pfx_i\)
因此我们最后要统计的就是这些位置的信息，考虑用线段树维护的话难点在于合并两个区间的答案，显然我们不可能把一个区间内所有的前缀最小值点都存下来
考虑如果我们和一般的线段树一样，只维护区间最小值和修改的懒标记，有没有什么方法可以快速从这些信息推出答案呢
可以考虑递归求解，假设存在函数\(F(x,k)\)表示在线段树节点\(x\)对应的区间中，前缀最小值的值\(<k\)的点的信息
同时令\(mi_x\)表示线段树节点\(x\)对应的区间中的最小值，\(o(x)\)表示线段树节点\(x\)对应的区间中的前缀最小值的信息，则我们可以分类讨论：
- 若\(k\le mi_x\)，则说明左边区间没有任何贡献，\(F(x,k)=F(rs_x,k)\)
- 若\(k>mi_x\)，则说明可以直接调用右边区间的贡献，\(F(x,k)=F(ls_x,k)+o(x)-o(ls_x)\)
这样我们可以每次\(O(\log n)\)的完成一次pushup操作，因此最后的总复杂度就是\(O(n\log^2 n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int n,m,opt,x; char ch[10],s[N];
struct ifo
{
int num,xsum;
inline ifo(CI NUM=0,CI XSUM=0)
{
num=NUM; xsum=XSUM;
}
friend inline ifo operator + (const ifo& A,const ifo& B)
{
return ifo(A.num+B.num,A.xsum^B.xsum);
}
friend inline ifo operator - (const ifo& A,const ifo& B)
{
return ifo(A.num-B.num,A.xsum^B.xsum);
}
}a[N],b[N];
class Segment_Tree
{
private:
int mi[N<<2],tag[N<<2]; ifo st[N<<2],o[N<<2];
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void apply(CI now,CI mv)
{
mi[now]+=mv; tag[now]+=mv;
}
inline void pushup(TN)
{
int mid=l+r>>1; mi[now]=min(mi[now<<1],mi[now<<1|1]);
o[now]=o[now<<1]+query(mi[now<<1],RS);
}
inline void pushdown(CI now)
{
if (tag[now]) apply(now<<1,tag[now]),apply(now<<1|1,tag[now]),tag[now]=0;
}
public:
inline void build(ifo *a,TN)
{
o[now]=st[l]=a[l]; if (l==r) return; int mid=l+r>>1; build(a,LS); build(a,RS);
}
inline void modify(CI beg,CI end,CI mv,TN)
{
if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS); pushup(now,l,r);
}
inline ifo query(CI pre,TN)
{
if (l==r) return mi[now]<pre?st[l]:ifo(0,0); int mid=l+r>>1; pushdown(now);
if (pre<=mi[now<<1]) return query(pre,RS); else return query(pre,LS)+o[now]-o[now<<1];
}
#undef TN
#undef LS
#undef RS
}A,B;
int main()
{
//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) a[i]=ifo(1,i),b[i]=ifo(1,n-i+1);
for (A.build(a),B.build(b),i=1;i<=m;++i)
{
scanf("%d%d",&opt,&x);
if (opt==1)
{
scanf("%s",ch+1); s[x]=ch[1];
if (s[x]=='(') A.modify(x,n,1),B.modify(n-x+1,n,-1);
else A.modify(x,n,-1),B.modify(n-x+1,n,1);
} else
{
if (s[x]=='(') A.modify(x,n,-1),B.modify(n-x+1,n,1);
else A.modify(x,n,1),B.modify(n-x+1,n,-1);
}
ifo ans=A.query(0)+B.query(0);
printf("%d %d\n",ans.num,ans.xsum);
}
return 0;
}
H. 课件设计
超级傻逼题，但我不会写NTT模板苦路西
首先不妨设\(f_i\)表示最后做了\(i\)个重复课件的概率，则最后的答案就是\(\frac{1}{\sum_{i=0}^{\lfloor \frac{n}{2} \rfloor}f_i}\)
而\(f_i\)的求法有个很显然的暴力，然后这个东西一眼发现此时就是\(\prod_{i=1}^n [(1-k_i\times p_i)+(k_i\times p_i)\times x]\)这个多项式\([x^i]\)的系数，直接分治NTT即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=400005,mod=998244353;
int n,x,P[N]; VI v[N];
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y)
{
return x-y<0?x-y+mod:x-y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
namespace Poly
{
int lim,p,rev[N];
inline void init(CI n)
{
for (lim=1,p=0;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void NTT(int *f,CI opt)
{
RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int m=i<<1,D=quick_pow(3,opt==1?(mod-1)/m:mod-1-(mod-1)/m);
for (RI j=0;j<lim;j+=m)
{
int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);
}
}
}
if (!~opt)
{
int Inv=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;
}
}
}
using namespace Poly;
int ta[N],tb[N];
inline VI merge(const VI& A,const VI& B)
{
RI i; int n=A.size(),m=B.size(); init(n+m-1); VI C;
for (i=0;i<n;++i) ta[i]=A[i]; for (i=n;i<lim;++i) ta[i]=0;
for (i=0;i<m;++i) tb[i]=B[i]; for (i=m;i<lim;++i) tb[i]=0;
for (NTT(ta,1),NTT(tb,1),i=0;i<lim;++i) ta[i]=1LL*ta[i]*tb[i]%mod;
for (NTT(ta,-1),i=0;i<n+m-1;++i) C.push_back(ta[i]); return C;
}
inline VI solve(CI l,CI r)
{
if (l==r) return v[l]; int mid=l+r>>1;
return merge(solve(l,mid),solve(mid+1,r));
}
int main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&x),P[i]=quick_pow(x);
for (i=1;i<=n;++i) scanf("%d",&x),P[i]=1LL*P[i]*quick_pow(x)%mod;
for (i=1;i<=n;++i) v[i].resize(2),v[i][0]=sub(1,P[i]),v[i][1]=P[i];
VI res=solve(1,n); int ans=0;
for (i=0;i<=n/2;++i) ans=sum(ans,res[i]);
return printf("%d",ans?quick_pow(ans):-1),0;
}
Postscript
被虐惨了，下次一定跟榜做题，再把板子准备好苦路西