UOJ Logo hzoi2017_csm的博客

博客

蒟蒻求教

2019-04-15 16:20:49 By hzoi2017_csm

今天被同学丢了一道题:

两个长度为$n$的数组的内积定义为$\sum_{i=1}^n a_ib_i$。

假如我们改变两个数组中元素的顺序,不难发现两数组同是递增时内积最大,一个递增一个递减时内积最小。

如果算入相同的内积取值,一共有$n!$个数,那么这$n!$个数中第$k$大的是多少呢?

$k$的范围可以是$1e5$或者$1e9$等等,不设上限,$n$同样不设上限。

本人太弱了,目前没有找到比$O(n!)$更优的算法。

自从来到UOJ这个宝地,我的视野变得开阔了,也见识了几位数学大佬,其中肯定不乏富有人类智慧的人士。我相信大佬们一定能给我满意的答案!

求大佬教。

【bzoj4321】queue2 递推式求助

2018-08-14 09:28:33 By hzoi2017_csm

【bzoj4321】queue2 题目描述

n 个沙茶,被编号 1~n。排完队之后,每个沙茶希望,自己的相邻的两人只要无一个人的编号和自己的编号相差为 1(+1 或-1)就行; 现在想知道,存在多少方案满足沙茶们如此不苛刻的条件。 输入

只有一行且为用空格隔开的一个正整数 N,其中 100%的数据满足 1≤N ≤ 1000; 输出

一个非负整数,表示方案数对 7777777 取模。

样例输入 4

样例输出 2

如上,本题正解为DP $O(n^2)$,但oeis给出了递推式

$a_n=(n+1)a_{n-1}−(n−2)a_{n−2}−(n−5)a_{n−3}+(n−3)a_{n−4} $

自己太弱了理解不了,有大佬能给出递推式的证明吗

共 2 篇博客