111qqz的小窝

老年咸鱼冲锋!

hdu 5145 NPY and girls

http://acm.hdu.edu.cn/showproblem.php?pid=5145
题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

思路:正好刚刚听完学堂在线上的组合数学的那一节,讲到有重复元素的不重复排列的个数的计算方法:可以先将所有元素看成不重复,再除以每个元素的重复度的阶乘(重复度定义为每个元素个数)。

增加一个元素的影响是,乘一个增加的长度,并且除以该元素的重复度(因为每增加一个元素就要除以以此重复度,那么当同一元素c增加到第i次时,除以的就是i的阶乘),减少一个元素的影响正相反。 两种改变都可以O(1)实现,因此可以上莫队。

之前要预处理下逆元。

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz