做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2277. -- 逆序对的和

2277: 逆序对的和

时间限制: 1 Sec  内存限制: 128 MB
提交: 56  解决: 22
[上一题][提交][讨论版][状态][下一题]

题目描述

给定一个序列a1,a2,a3,……,an,如果存在i<j,并且ai>aj,那么我们称之为逆序对。逆序对中含有第i个数,则这个逆序对是第i个数的逆序对。对于给定序列,所有m的倍数的逆序对的数量之和是多少? (提示:n=5,m=2时,求的是第2个数的逆序对与第4个数的逆序对的和,允许重复)

输入

第一行:输入一个正整数n和一个正整数m

接下来n行,每行一个整数。

输出

输出一个整数。

样例输入

5 2
-1
9
1
2
0

样例输出

5

提示

n以内m的倍数有2,4;
第2个数的逆序对有3个,分别是9和1,9和2,9和0
第4个数的逆序对有2个,分别是9和2, 2和0
这两个数的逆序对数量之和为3+2=5,所以输出5。
【数据范围】
30%的数据:m = 1,100%的数据:m < 10
数据1-10:n <= 5000,|ai|<=n,数据随机生成
数据11-12:n <= 10000,|ai|<=n,数据随机生成
数据13-14:n <= 50000,|ai|<=n,数据随机生成
数据15-16:n <= 100000,|ai|<=n,不重复,数据随机生成
数据17-18:n <= 100000,|ai|<2^31,不重复,数据随机生成
数据19-20:n <= 100000,|ai|<2^31,有重复,数据随机生成

标签

[上一题][提交][讨论版][状态][下一题]