在门户网站建设上的讲话,工商银行网页版官网,医院网站建设方案书,济南网站建设要多少钱题目链接#xff1a;https://www.luogu.com.cn/problem/P8649
思路#xff1a; 看到区间和#xff0c;第一反应肯定是前缀和#xff0c;我们求出前缀和后对前缀和数组每一个值模k#xff0c;然后对一个数组的值查看前面有几个相同的#xff0c;举个例子#xff1a;…题目链接https://www.luogu.com.cn/problem/P8649
思路 看到区间和第一反应肯定是前缀和我们求出前缀和后对前缀和数组每一个值模k然后对一个数组的值查看前面有几个相同的举个例子 样例中前缀和数组a取模后为1 1 0 0 1 下标依次为1 2 3 4 5 当题目所求子序列以a5结尾时已知a51且a5前面与a5相同的值有2个则以a5结尾可以获得2个满足题目要求的区间 如果以a3结尾则是一个因为实际上有一个a00。
#includebits/stdc.husing namespace std;using ll long long;
const ll N 3e5 5;
const ll mod 1e9 7;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}void solve() {int n; cin n;ll k; cin k;vectorlla(n 1);vectorllpre(n 1);vectorllcnt(n 1);for (int i 1; i n; i) {cin a[i];pre[i] pre[i - 1] a[i];}ll ans 0;cnt[0] 1;for (int i 1; i n; i) {ans cnt[pre[i] % k];cnt[pre[i] % k];}cout ans \n;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);std::cout.tie(0);int t1 1;//cin t1;while (t1--)solve();return 0;
}
