HDU5496 – Beauty of Sequence(找规律递推)

HDU5496

【中文题意】

【分析】表示看不懂题解，自己想了一种解法：

首先，如果没有重复的数字，则有递推公式:f[i] = f[i-1]*2+a[i]*i(i从0开始);这个公式自己画一下所有方案就能得出了。

而对于有重复的情况，只要每次减去sum{2^j}其中j < i && a[j] == a[i]；那么用个数字记录下sum就可以了，具体画一下所有方案就能看出来了。由于要离散化复杂度O(n)*log(n)；用HASH会更快点。

【AC CODE】546ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MOD = 1e9+7, MAXN = 1e5+10;
int a[MAXN],sot[MAXN],b[MAXN],cnt[MAXN];

int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    b[0] = 1;
    repe(i,1,100000) b[i] = (b[i-1]<<1)%MOD;
    while(t--)
    {
        int n;
        scanf("%d", &n);
        rep(i,0,n) scanf("%d", &a[i]),sot[i] = a[i];
        sort(sot,sot+n);
        int len = unique(sot,sot+n)-sot;
        clc(cnt,0);
        LL ans = 0;
        rep(i,0,n)
        {
            int v = lower_bound(sot,sot+len,a[i])-sot;
            LL tmp = 0;
            if(cnt[v]) tmp = (LL)(cnt[v])*a[i];
            cnt[v] = (cnt[v]+b[i])%MOD;
            ans = (ans*2+(LL)a[i]*b[i]-tmp)%MOD;
        }
        if(ans < 0)ans += MOD;
        printf("%I64d\n", ans);
    }
    return 0;
}