求助站外题

学术版

Register_int @ 2022-09-21 20:27:56

普及模拟 T4 都不会了
给定 n,m。将所有四元组 (i+j+k,i,j,k) 按照字典序排列，其中 1\le i,j,k\le n。要求出第 m 个四元组。复杂度要求 O(n)。

by Register_int @ 2022-09-21 20:28:44

我只会暴力淦柿子然后 O(n^2)

by houzhiyuan @ 2022-09-21 20:31:26

直接考虑枚举第一维，算第一维是 i 有多少种方案，用容斥算一下，然后再去确定后面的就好了，这个东西可以 O(n)。

by Register_int @ 2022-09-21 20:33:37

@houzhiyuan 能具体说说嘛 /bx/bx/bx

by houzhiyuan @ 2022-09-21 20:37:46

就是设 f_x 表示 i+j+k=x 的方案数，然后这个东西可以容斥算，考虑有多少个数大于 n，可以得到 f_x=\binom{x-1}{2}-3\binom{x-n-1}{2}+3\binom{x-2n-1}{2} （式子应该是对的）。

然后知道这个东西就可以求出第一维了，然后后面的直接枚举第二维是什么，同理算方案即可。

by luogubot @ 2022-09-21 20:38:23

好像是一年前的某道 abc。

by luogubot @ 2022-09-21 20:40:36

https://atcoder.jp/contests/abc200/tasks/abc200_e

by luogubot @ 2022-09-21 20:40:41

@Register_int

by Register_int @ 2022-09-21 20:50:36

@luogubot 51Nod 又出原题/oh

by Register_int @ 2022-09-21 20:51:09

@houzhiyuan 谢谢大佬 /bx/bx/bx

|