外贸网站dns,wordpress前台修改用户头像,做网站不挣钱,优秀的网站正题
题目链接:https://ac.nowcoder.com/acm/contest/1103/A 题目大意
将一个长度为nnn的数组复制成kkk份#xff0c;然后每个区间的值是一个区间中不同的数的数量#xff0c;求每个非空区间的值和。 解题思路
若一个区间长度nnn那么他们的值是固定的#xf…正题
题目链接:https://ac.nowcoder.com/acm/contest/1103/A 题目大意
将一个长度为nnn的数组复制成kkk份然后每个区间的值是一个区间中不同的数的数量求每个非空区间的值和。 解题思路
若一个区间长度nnn那么他们的值是固定的所以我们可以先计算出这些区间的答案。
现在只需要考虑长度nnn的区间我们讲原数组复制一份放到后面后我们用fif_ifi表示第iii个结尾的区间权值和。若不考虑iii这个位置的贡献那么fifi−1f_if_{i-1}fifi−1iii这个位置影响的区间是到上一个和它相同的位置lastlastlast。也就是fifi−1i−lastf_if_{i-1}i-lastfifi−1i−last。
当ininin时我们不能计算左端点nnn的区间所以我们就改为fifi−1max{n−last,0}f_if_{i-1}max\{n-last,0\}fifi−1max{n−last,0}即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510,XJQ1e97;
ll n,k,a[N],ans,num,b[N],v[N];
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
int main()
{scanf(%lld%lld,n,k);for(ll i1;in;i)scanf(%lld,a[i]),b[i]a[i];sort(b1,b1n);ll cntunique(b1,b1n)-b-1;for(ll i1;in;i){a[i]a[in]lower_bound(b1,b1cnt,a[i])-b;if(!v[a[i]]) v[a[i]]i,num;}ansnum*n%XJQ*n%XJQ;ansans*max((k-2)*(k-1)%XJQ,0ll)%XJQ*power(2,XJQ-2)%XJQ;memset(v,0,sizeof(v));num0;ll sum0,z0;for(ll i1;i2*n;i){ll last0;if(v[a[i]]) lastv[a[i]];v[a[i]]i;if(in) zmax(n-last,0ll);else zi-last-(in);(sumz*(k-(in))%XJQ)%XJQ;}printf(%lld,(anssum)%XJQ);
}
