1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 #include<map>11 using namespace std;12 #define N 5001013 #define LL long long14 #define INF 0xfffffff15 const double eps = 1e-8;16 const double pi = acos(-1.0);17 const double inf = ~0u>>2;18 int a[N];19 int dp[N];20 int num[2][300],last[N];21 map<int,int>f;22 int main()23 {24     int i,j,n;25     while(scanf("%d",&n)!=EOF)26     {27         f.clear();28         int g =0 ;29         for(i = 1; i<= n ;i++)30         {31             scanf("%d",&a[i]);32             if(!f[a[i]])33             {34                 f[a[i]] = ++g;35                 a[i] = g;36             }37             else a[i] = f[a[i]];38         }39         for(i = 1; i <= n; i++)40         dp[i] = INF;41         memset(last,-1,sizeof(last));42         memset(num,0,sizeof(num));43         int k = sqrt(n*1.0)+1;44         int tk = 1;45         dp[1] = 1;46         last[a[1]] = 1;47         num[1][1] = 1;48         dp[0] = 0;49         for(i = 2; i <= n ;i++)50         {51             if(last[a[i]]==-1)52             {53                 tk+=1;54                 num[i%2][1] = i;55                 for(j = 1; j <= min(tk-1,k-1) ; j++)56                 num[i%2][j+1] = num[(i-1)%2][j];57             }58             else59             {60 61                 num[i%2][1] = i;62                 for(j = 1; j < min(k,tk) ; j++)63                 {64                     if(last[a[i]]==num[(i-1)%2][j]) break;65                     num[i%2][j+1] = num[(i-1)%2][j];66                 }67                 for(int g = j+1 ; g <= min(tk,k) ; g++)68                 num[i%2][g] = num[(i-1)%2][g];69             }70             last[a[i]] = i;71             for(j = 1; j <= min(k,tk); j++)72             {73                 int po = num[i%2][j+1];74                 dp[i] = min(dp[i],dp[po]+j*j);75                // cout<<dp[po]<<" "<<po<<endl;76             }77         }78         printf("%d\n",dp[n]);79 80     }81     return 0;82 }

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 12 12 #define LL __int64 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 #define mod 10000007 18 struct Mat 19 { 20     LL mat[N][N]; 21 }; 22 int n; 23 int a[N]; 24 Mat operator * (Mat a,Mat b) 25 { 26     Mat c; 27     memset(c.mat,0,sizeof(c.mat)); 28     int i,j,k; 29     for(k =0 ; k < n ; k++) 30     { 31         for(i = 0 ; i < n ; i++) 32         { 33             if(a.mat[i][k]==0) continue;//优化 34             for(j = 0 ; j < n ; j++) 35             { 36                 if(b.mat[k][j]==0) continue;//优化 37                 c.mat[i][j] = (c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod; 38             } 39         } 40     } 41     return c; 42 } 43 Mat operator ^(Mat a,int k) 44 { 45     Mat c; 46     int i,j; 47     for(i =0 ; i < n ; i++) 48         for(j = 0; j < n ; j++) 49             c.mat[i][j] = (i==j); 50     for(; k ; k >>= 1) 51     { 52         if(k&1) c = c*a; 53         a = a*a; 54     } 55     return c; 56 } 57 int main() 58 { 59     int m,i,j; 60     Mat c; 61     while(scanf("%d%d",&n,&m)!=EOF) 62     { 63         memset(c.mat,0,sizeof(c.mat)); 64         for(i = 0 ; i <= n; i++) 65         { 66             c.mat[0][i] = 10; 67             for(j = 1 ; j <= i ; j++) 68                 c.mat[j][i] = 1; 69         } 70         for(i = 0 ; i <= n ; i++) 71             c.mat[n+1][i] = 3; 72         c.mat[n+1][n+1] = 1; 73         LL s = 233; 74         Mat ans; 75         memset(ans.mat,0,sizeof(ans)); 76         ans.mat[0][0] = s; 77         for(i = 1; i <= n; i++) 78         { 79             scanf("%d",&a[i]); 80             s+=a[i]; 81             s%=mod; 82             ans.mat[0][i] = s; 83         } 84         ans.mat[0][n+1] = 1; 85         int tn = n; 86         n+=2; 87         if(m>1) 88         ans = ans*(c^(m-1)); 89 //        for(i = 0 ; i < n ; i++) 90 //            {for(j = 0; j< n ; j++) 91 //        cout<<c.mat[i][j]<<" "; 92 //        puts(""); 93 //            } 94 //        for(i = 0 ; i < n ; i++) 95 //        { 96 //            for(j = 0; j < n ; j++) 97 //                cout<<ans.mat[i][j]<<" "; 98 //            puts(""); 99 //        }100         printf("%I64d\n",ans.mat[0][tn]);101     }102     return 0;