題目鏈接：https://www.luogu.com.cn/problem/P8649

思路：
?? ?看到區間和，第一反應肯定是前綴和，我們求出前綴和后對前綴和數組每一個值模k，然后對一個數組的值查看前面有幾個相同的，舉個例子：

?? ?樣例中前綴和數組a取模后為：1 ? ?1 ? ?0 ? ?0 ? ?1

?? ?下標依次為1 2 3 4 5

?? ?當題目所求子序列以a5結尾時，已知a5=1且a5前面與a5相同的值有2個，則以a5結尾可以獲得2個滿足題目要求的區間
?? ?
?? ?如果以a3結尾則是一個，因為實際上有一個a0=0。
?

#include<bits/stdc++.h>using 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;vector<ll>a(n + 1);vector<ll>pre(n + 1);vector<ll>cnt(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;
}