F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 5342 >> 数据有问题
save_code @ 2018-05-23 10:29:47
[ Quote ] [ Edit ] [ Delete ] 1#
对于所有测试数据,1 ≤ T ≤ 100,1 ≤ N ≤ 50000, 1 ≤ Li, j ≤ j

测试数据中 有 Li,j >j 的数据
save_code @ 2018-05-23 10:45:37
[ Quote ] [ Edit ] [ Delete ] 2#
分治+FFT 预处理 然后 基本上直接输出答案啊。。。

dp[i]=i!-sigma(dp[j]*c[i-1][j-1]) 2<=j<=i-1

式子没推错吧
save_code @ 2018-05-23 11:28:50
[ Quote ] [ Edit ] [ Delete ] 3#
果然错了。。。。
save_code @ 2018-05-23 15:33:49
[ Quote ] [ Edit ] [ Delete ] 4#
5W的表让不让交啊???
save_code @ 2018-05-23 16:24:29
[ Quote ] [ Edit ] [ Delete ] 5#
N^2的 滚动数组 可以跑一张表,就是不知道 这么大能否提交
save_code @ 2018-05-24 10:52:59
[ Quote ] [ Edit ] [ Delete ] 6#
数据读入了 一半 判0 跳出了。。。。晕死
save_code @ 2018-05-24 11:08:20
[ Quote ] [ Edit ] [ Delete ] 7#
算法, 长度为N的 (1,1,1,1....N)的序列 种类为dp[N]
dp[N] 可以由两类序列得到 最后一个数字 一定是 [2,N-2]

第一类是 dp[N-1]*(N-2) 第二类 序列式 中间 恰有 一个 长度为 y 的连续的子列

这个 种类数 就是 dp[n-y+1]*dp[y] 将每一种 排列好的这种序列 中 y的最后 一个数字 放到 倒数第二个 格子 恰好 形成一个合法的序列 当然 y个子序列的选法为 n-y-1 因为 排列好的 n-y+1个数字中最后一个 和倒数第二个 数字不能选

所以公式就是 dp[N]==dp[N-1]*(N-2)+sigma((N-y-1)*dp[N-y+1]*dp[y]

一开始 把系数 N-y-1搞成了 N-y对拍了很久没发现错误
save_code @ 2018-05-24 11:19:51
[ Quote ] [ Edit ] [ Delete ] 8#
最后 一个 位置 和 dp[N-1]*(N-2)冲突(因为 我们要将不合法的序列转化成合法的),倒数第二个位置 刚好形成 [1,N-1]连续 两个位置都不合法
[Top] [Previous Page] [Next Page]

HOME Back