psd简单的网站首页,wordpress手机如何登陆,企业网站申请流程,网站地图怎么制作输入
5 2
1 2 3 4 5
输出
6
思路#xff1a;首先由连续子串和可以想用前缀和#xff0c;由于加减法总和取模和分别取模结果不受影响#xff0c;所以我们前缀和之后直接取模方便观察性质#xff0c;本题前缀和#xff1a;1#xff0c;3#xff0c;6#xff0c;10#…
输入
5 2
1 2 3 4 5
输出
6
思路首先由连续子串和可以想用前缀和由于加减法总和取模和分别取模结果不受影响所以我们前缀和之后直接取模方便观察性质本题前缀和1361015取模之后11001用差分就可以求出某段区间的和如果该段区间和取模2为0那么答案1但是如果直接for循环差分o(N**2)会超时不妨找取模后的数组中相等的数因为这样两数相减0取模后为0那么没取模的时候一定是2的倍数即可只要o(n).
细节
1由于差分找到的区间的左开右闭的当有独立的前缀和0那么从一开始到它这段连续序列是可以的未来避免单独讨论在读入a[N],s[N]时我们从1 开始最后找相同数字时我们从 0 开始。
2ansc[sum[i]]; c[sum[i]];这个顺序不能反只有碰到2个相等才能有效
#includebits/stdc.h
using namespace std;
#define int long long
const int N1e510;
int n,k,ans0;
int a[N],sum[N],c[N];
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnk;for(int i1;in;i){cina[i];sum[i]sum[i-1]a[i];//sum[i-1]0sum[i]%k;}for(int i0;in;i ){ansc[sum[i]];c[sum[i]];}coutansendl;return 0;}
