4547: Hdu5171 小奇的集合
Time Limit: 2 Sec Memory Limit: 256 MB
Submit: 263 Solved: 113
[Submit][Status][Discuss]
Description
有一个大小为n的可重集S,小奇每次操作可以加入一个数a+b(a,b均属于S),求k次操作后它可获得的S的和的最大
值。(数据保证这个值为非负数)
Input
第一行有两个整数n,k表示初始元素数量和操作数,第二行包含n个整数表示初始时可重集的元素。
对于100%的数据,有 n<=10^5,k<=10^9,|ai|<=10^5
Output
输出一个整数,表示和的最大值。答案对10000007取模。
Sample Input
2 2
3 6
3 6
Sample Output
33
HINT
Source
思路:同hdu 5171的区别在于,a可能为负数。
同样是设a0为次大值,a1为最大值。
根据a0,a1的正负分类讨论。
如果a1<0(此时a0一定也小于0)那么每次操作都是a0+a1,因为越加越小。
如果a0<0,需要计算需要几次运算,使得a0>=0。设需要num次。
原因是,类斐波那契数列的性质可以对于正数,也可以对于负数,但是如果有正数有负数,性质是不满足的。
因此如果num>k,说明一直都是负数,直接运算即可,如果num<=k,就需要先把负数部分用等差数列的方法处理掉。
然后再用矩阵快速幂的方法计算剩下的k-num次。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 |
/* *********************************************** Author :111qqz Created Time :Tue 25 Oct 2016 07:00:23 PM CST File Name :code/bzoj/4547.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const LL mod = 1E7+7; const int N=1E5+7; int n,k; LL a[N]; LL a0,a1; LL sum; struct Mat { LL mat[2][2]; void clear() { ms(mat,0); } }M,M1; Mat operator*(Mat a,Mat b) { Mat res; res.clear(); for ( int i = 0 ; i < 2 ; i++) for ( int j = 0 ; j < 2 ; j++) for ( int k = 0 ; k < 2 ; k++) res.mat[i][j] = (res.mat[i][j] + a.mat[i][k]*b.mat[k][j] ) %mod; return res; } Mat operator ^ (Mat a,LL b) { Mat res; res.clear(); for ( int i = 0 ; i < 2 ; i++) res.mat[i][i] = 1; while (b>0) { if (b&1) res = res * a; b = b >> 1LL; a = a * a; } return res; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif scanf("%d%d",&n,&k); for ( int i = 1 ; i <= n ;i++) scanf("%lld",&a[i]); sum = 0 ; sort(a+1,a+n+1); a0 = a[n-1]; a1 = a[n]; //cout<<"a0:"<<a0<<" a1:"<<a1<<endl; // if (a1<0) { for ( int i = 1 ; i <= n ; i++) sum = ( sum + a[i] + mod ) %mod; sum = (sum + k*(a0+a1+mod)%mod+mod)%mod; printf("%lld\n",sum); return 0; } for ( int i = 1 ;i <= n-2 ; i++) sum =( sum + a[i]+mod ) % mod; if (a0<0) { LL num = -a0/a1+1; // cout<<"num:"<<num<<endl; if (num<=k) { k-=num; sum = ( sum + num*a0%mod + (a1*(num-1))*num/2%mod +mod)%mod; a0 = (a0 + a1 *num%mod)%mod; if (a0>a1) swap(a0,a1); } } Mat ans; M.clear(); M1.clear(); ans.clear(); M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1; M1.mat[0][0] = a0; M1.mat[1][0] = a1; ans = (M^(k+2))*M1; sum = (sum + ans.mat[1][0] - a1 + mod)%mod; printf("%lld\n",sum); return 0; /* if (a0<0) { LL num = (-a0)/a1 + 1; // cout<<"num:"<<num<<endl; if (k<=num) { for ( int i = 1 ; i <= n-2 ; i++) sum = (sum + a[i] + mod ) % mod; sum = ( sum + a[n] + mod ) %mod; num = k+1; // cout<<"sum:"<<sum<<endl; sum = (sum + (num*a0 + num*(num-1)/2*a1)%mod+mod)%mod; printf("%lld\n",sum); return 0; } k-=num; for ( int i = 1 ; i <= n-2 ; i++) sum = (sum + a[i]+mod ) % mod; sum = (sum + num*a0 + num*(num-1)/2*a1+mod)%mod; a0 = a0 + num*a1; //<F5printf("a0:%lld a1:%lld\n",a0,a1); Mat ans; M.clear(); M1.clear(); ans.clear(); M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1; M1.mat[0][0] = a0; M1.mat[0][1] = a1; ans = (M ^(k+2))*M1; sum = (sum + ans.mat[1][0] - a1 + mod ) %mod; printf("%lld\n",sum); } */ #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!