JZOJ
最新推荐文章于 2018-12-01 17:47:55 发布
HuangXinyue1017 于 2018-10-28 10:35:30 发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
Time Limits: 2000 ms Memory Limits: 524288 KB Description
院子落叶，跟我的思念厚厚一叠；窗台蝴蝶，像诗里纷飞的美丽章节……
Input
小 H 是一个喜欢养花的女孩子。
她买了 n 株花，编号为一里香，二里香……七里香……n 里香，她想把这些花分别种在 n个不同的花盆里。
对于一种方案，第 i 个花盆里种的是 ai 里香，小 H 定义其美丽值为：
第一行一个整数 n，第二行有 n 个整数表示 {pi}。pi表示第i个花盆里不可以种ai里香
Output
一个整数，表示答案对 109 + 9 取模的结果。
Sample Input
3
2 1 3
Sample Output
7
Data Constraint
对于 30% 的数据，n ≤ 16。
对于 60% 的数据，n ≤ 100。
对于 100% 的数据，n ≤ 5000，{pi} 是一个排列。
Solution
这题嘛，DP啊……菜鸡的我只会写暴力 设 f i , j f_{i,j} fi,j 表示一共有 ( i + j ) (i+j) (i+j) 个元素，其中 i i i 个元素有位置上的限制， j j j 个元素没有位置限制 有限制指的假定待放入元素为 x x x ，存在位置 p k = x p_k=x pk=x ，而第 k k k 个位置还没有填入元素 这样我们就有转移式 f 0 , 0 = 1 ， f 1 , 0 = 0 ， f 0 , 1 = 1 ， f 0 , 2 = 2 f_{0,0}=1，f_{1,0}=0，f_{0,1}=1，f_{0,2}=2 f0,0=1，f1,0=0，f0,1=1，f0,2=2 f x , 0 = ( x − 1 ) ( f x − 1 , 0 + f x − 2 , 0 ) f_{x,0}=(x-1)(f_{x-1,0}+f_{x-2,0}) fx,0=(x−1)(fx−1,0+f 相关知识
JZOJ 3887. 【长郡NOIP2014模拟10.22】字符串查询
网址: JZOJ https://m.huajiangbk.com/newsview1492985.html
