Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5449 --合法序列
5449: 合法序列
警告!
题目
状态
题解
题目描述
给你一个长度为 $N$ 的正整数序列,如果一个连续的子序列,子序列的和能够被 $K$ 整除,那么就视此子序列合法,求原序列包括多少个合法的连续子序列? 对于一个长度为 $8$ 的序列,$K=4$ 的情况:$2,1,2,1,1,2,1,2$。它的答案为 $6$,子序列位置是 $1\to 8$,$2\to 4$,$2 \to 7$,$3\to 5$,$4 \to 6$,$5\to 7$。
输入
第一行有一个正整数 $T$,表示数据组数。 接下来,对于每组数据: 第一行有 $2$ 个正整数,$K,N$。 第二行有 $N$ 个数,表示这个序列。
输出
对于每组数据,输出一行一个整数,表示答案。
样例输入输出
输入#1
复制
2 7 3 1 2 3 4 8 2 1 2 1 1 2 1 2
输出#1
复制
0 6
提示
对于 $30\%$ 的数据,满足$1 \leq T \leq 10$,$1 \leq N,K \leq 1000$; 对于 $100\%$ 的数据,满足$1 \leq T \leq 20$,$1\leq N \leq 50000$,$1 \leq k \leq 10^6$,序列的每个数$\leq 10^9$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和