牛客挑战赛32

Source

牛客挑战赛32

代码见我(zory)的提交

A AK

B 114514

此题需要int128

C 斐波那契数列卷积

此题的正解应该是考虑组合意义,我是直接oeis的

D 放物品

请先思考后再展开

感觉百度之星复赛的故事再一次重演了,被有区分的讨论题搞了2h,后面1h是因为mod太多没看到多写了一个2,然后到外面思考人生了
我的做法需要你能扎实地理解错排D的递推式怎么推,具体见oi之路
错排本质上是n人n个不重叠限制,然后下面还要用到n-1个和n-2个限制,分别设为f和g,然后我一开始的做法要所有f和g,所以就推了一波递推式,结果多写了个2(有点像烧情侣的一道题,也在错排那里);因为限制不满,会有人和位置空闲
$f_n=D_{n-1}+f_{n-1}*(n-1)$,即考虑空出来的人是否在空出来的位置上

$g_n=P_{n-2}^2*g_{n-2}+2*f_{n-1}+4*D_{n-1}$,也就是考虑空出来两个位置都空、都不空、恰一个空,这里恰一个空的话剩下n-1个人和n-1个限制(新限制是另一个空人不能在另一个空位置上)

那么求答案的话考虑数对i和j,$j>i,pos_j<pos_i$的贡献,然后你把暴力写了优化一下即可,具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ll p[N],D[N],F[N],G[N],pre[N],pre2[N];
void main()
{
D[0]=1,D[1]=0;for(int i=2;i<N;i++) D[i]=ll(i-1)*(D[i-1]+D[i-2])%MOD;
F[0]=1,F[1]=1;for(int i=2;i<N;i++) F[i]=( D[i-1]+F[i-1]*(i-1) )%MOD;
G[0]=1,G[1]=1;for(int i=2;i<N;i++) G[i]=( G[i-2]*(i-2)%MOD*(i-3)%MOD+4*D[i-1]%MOD+MOD+2*D[i-2]%MOD )%MOD;
pre[0]=0;for(int i=1;i<N;i++) pre[i]=mm(pre[i-1]+i);
int T=qread();
while(T--)
{
int n=qread();for(int i=1;i<=n;i++) p[i]=qread();
if(n<=1){puts("0");continue;}
for(int ln=1;ln<=n;ln++) pre2[ln]=(pre2[ln-1]+1ll*ln*(n-ln))%MOD;
ll ans=0;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
{
ll cnt=pre2[n-1];
if(p[j]<p[i]) add(cnt, MOD-(p[i]-p[j]) );
add(cnt, 1ll*MOD-mm( pre[n-p[j]]+MOD-(p[j]<p[i]?p[i]-p[j]:0) ) );
add(cnt, 1ll*MOD-mm( pre[p[i]-1]+MOD-(p[j]<p[i]?p[i]-p[j]:0) ) );
if(p[i]<p[j]) add(cnt, MOD-(p[j]-p[i]) );
add(cnt, 1ll*MOD-mm( pre[n-p[i]]+MOD-(p[i]<p[j]?p[j]-p[i]:0) ) );
add(cnt, 1ll*MOD-mm( pre[p[j]-1]+MOD-(p[i]<p[j]?p[j]-p[i]:0) ) );
ll sum=0;
add(sum, cnt*G[n-2]%MOD );if(p[i]<p[j]) add(sum, (p[j]-p[i])*D[n-2]%MOD );
add(sum, ( pre[n-p[i]]+MOD-(p[i]<p[j]?p[j]-p[i]:0) )*F[n-2]%MOD );
add(sum, ( pre[p[j]-1]+MOD-(p[i]<p[j]?p[j]-p[i]:0) )*F[n-2]%MOD );
add(ans, sum*(j-i)%MOD );
}write2((ans%MOD+MOD)%MOD);
}
}//(ans+MOD)%MOD

E 树上逆序对

请先思考后再展开

其实我写复杂了,我考虑的是如果一个点选了,那么增量就是 【到根更小】-【子树更小】,然后这样有正有负不好搞,注意到k很小,那用sum(初始逆序对数),把它转正即可,于是就是个二选一的01背包,bitset优化即可

其实更加有脑子的方法是看原本我的贡献是【子树更小】,新贡献是【到根更小】,所以不需要上述思考;另外我脑残还写了个dfs序,其实如果对dfs灵活一点的话,搞个东西记录前面访问的所有,减去遍历子树后新产生的,这样一个dfs即可,短不少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct BIT
{
int bit[N];int lowbit(int x){return x&-x;}
void add(int x,int c){while(x<N)bit[x]+=c,x+=lowbit(x);}
int ask(int x){int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
}up,down;
vc<pr> b;int a[N];vc<int> to[N];int dfn[N],dfnid=0,siz[N];
void pre(int x,int fa)
{
dfn[x]=++dfnid;siz[x]=1;
for(int t=0;t<sz(to[x]);t++) if(to[x][t]!=fa) pre(to[x][t],x),siz[x]+=siz[to[x][t]];
}
bitset<M> bs;ll sum=0;int sm[N];
void dfs(int x,int fa)
{
int num=lower_bound(all(b),MP(a[x],0))-b.begin()+1;
up.add(num,1);for(int t=0;t<sz(to[x]);t++) if(to[x][t]!=fa) dfs(to[x][t],x),siz[x]+=siz[to[x][t]];up.add(num,-1);
int add=up.ask(num-1)-sm[x],add2=0;if(add<0) {add2-=add;sum+=add;add=0;}GG(sum<0);
bs=(bs<<add)|(bs<<add2);
}
void main()
{
int n=qread();for(int i=1;i<=n;i++) a[i]=qread(),b.PB(MP(a[i],i));sort(all(b));
for(int i=1;i<n;i++){int x=qread(),y=qread();to[x].PB(y);to[y].PB(x);}pre(1,0);
for(int t=0;t<sz(b);t++)
{
int x=b[t].SE;
sm[x]=down.ask(dfn[x]+siz[x]-1)-down.ask(dfn[x]-1);
down.add(dfn[x],1);sum+=sm[x];
}
bs[0]=1;dfs(1,0);GG(sum<0);bs<<=sum;
int q=qread();while(q--){int k=qread();puts(bs[k]?"Orz":"QAQ");}
}//(ans+MOD)%MOD

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/145e.html
转载请注明出处,谢谢!