BZOJ3198: [Sdoi2013]spring

Time Limit: 40 Sec  Memory Limit: 256 MB

Description

Input

Output

Sample Input

3 3
1 2 3 4 5 6
1 2 3 0 0 0
0 0 0 4 5 6

Sample Output

2

HINT

Dragonite修正数据

Source

Hash

Solution

若求的是相同个数的正好为k的
但是有一对相同个数是k+p
那么在f[i]单次统计时会被统计C_{k+p}^{i}(k<=i<=k+p)
那么对于最终答案f[i]多统计了C_{i}^{k}
所以一对相同个数为k+p的就多统计了\sum_{i=k}^{k+p}C_i^k*C_{k+p}^{i}
但这些都是不合法的
运用容斥原理可以得到最终这对相同个数为k+p的统计了\sum_{i=k}^{k+p}C_i^k*C_{k+p}^{i}*(-1)^{i-k}
发现当k+p=k时即p=0时 这个式子值为1,否则为0。
这便符合我们的要求。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注