题目描述
有一个长为n×k的数组，它是由长为n的数组A1,A2,…,An重复k次得到的。
定义这个数组的一个区间的权值为它里面不同的数的个数，现在，你需要求出对于这个数组的每个非空区间的权值之和。
答案对109+7取模。
输入描述:
第一行两个整数n和k。
接下来一行n个整数，第i个整数为Ai。
输出描述:
输出一个整数，表示答案。
示例1
输入
2 2
1 2
输出
16
说明
数组为1, 2, 1, 2。
对于长为1的区间，共4个，权值为1。
对于长度>1的区间，可以发现权值均为2，共6个。
那么权值和为1×4+2×6=16。
备注:
对于前10%的数据n≤5。
对于前20%的数据n≤100。
对于前40%的数据n≤1000。
对于另外10%的数据n≤100,k=1。
对于另外10%的数据n≤1000,k=1。
对于另外10%的数据n≤105,k=1。
对于所有数据，1≤n≤105,1≤k≤109,1≤Ai≤109。
分析
反正我没打正解
如果k=1，那么我们可以转换角度考虑每种颜色的贡献。
对于每段区间，包含这个颜色则这个颜色对该区间的贡献为1，不包含这个颜色则这个颜色对该区间的贡献为0
所以就是要求取有多少段区间包含这个颜色，那么我们可以存下这个颜色在原数组的分布位置然后进一步讨论
假设分布的情况如下，白色代表其他颜色
现在考虑如何计数。我们可以固定区间的右端点，然后寻找包含这个颜色的左端点，比如
比如当右端点在[3,6]时，左端点的范围都是[1,3]，当右端点的范围在[7,9]时，左端点的范围都是[1,7]。
这样我们就这可以找出规律然后计算了（讲道理可以用总的合法的减去不合法的，但我没试过也不知道对不对
此时对于k=1时我们就可以解出来答案。
但是看到k≤109,把相同的数组拼接起来，貌似分类讨论挺麻烦的
可以试试递推
设f[k]表示k个数组拼起来的答案
对于新加入的数组，如果不看最右边的那一个，增加的贡献应该就是由k-2个数组拼成k-1个数组增加的贡献,即f[k-1]-f[k-2]
现在考虑最右边的数组，那么还没计算贡献的区间就是左端点在新加入的数组内，右端点在最右边数组内的区间
当k>=3时，显然这些区间都跨越了一个数组，贡献都是颜色总数，所以总的贡献为n*n*c（c为颜色总数）
所以得出递推是，f[k]=f[k-1]+f[k-1]-f[k-2]+n*n*c(k>=3),这东西可以矩阵加速。
对于f[1],f[2]，我们可以暴力求
然后，就没有然后了
Code
#include<map>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int maxn=100005;
int n,k,id,a[maxn<<1],f[5];
struct node{int mat[5][5];}x,y;
map<int,int>mp;vector<int>g[maxn];
node operator *(node a,node b)
{
node c;memset(c.mat,0,sizeof c.mat);
for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int k=1;k<=3;k++)
c.mat[i][k]=(c.mat[i][k]+1ll*a.mat[i][j]*b.mat[j][k]%mod)%mod;return c;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);a[i+n]=a[i];
if(!mp[a[i]])mp[a[i]]=++id;g[mp[a[i]]].push_back(i);
}
for(int i=1;i<=id;g[i].clear(),i++)
{
g[i].push_back(n+1);
for(int j=0,lim=g[i].size()-1;j<lim;j++)
f[1]=(f[1]+1ll*g[i][j]*(g[i][j+1]-g[i][j])%mod)%mod;
}
for(int i=1;i<=2*n;i++)g[mp[a[i]]].push_back(i);
for(int i=1;i<=id;g[i].clear(),i++)
{
g[i].push_back(2*n+1);
for(int j=0,lim=g[i].size()-1;j<lim;j++)
f[2]=(f[2]+1ll*g[i][j]*(g[i][j+1]-g[i][j])%mod)%mod;
}
x.mat[1][1]=f[1];x.mat[1][2]=f[2];x.mat[1][3]=1ll*n*n*id%mod;
y.mat[1][2]=-1;y.mat[2][1]=1;y.mat[2][2]=2;y.mat[3][2]=1;y.mat[3][3]=1;
k--;while(k){if(k&1)x=x*y;y=y*y;k>>=1;}
printf("%d
",x.mat[1][1]);
}