|
题目链接:http://poj.org/problem?id=3378
/**//* 题意: 给定N (1 <= N <= 50000) 个小于等于10^9的数Ai, 要求找出Crazy Thair的数量。 Crazy Thair是一个五元组{i, j, k, l, m}满足: 1. 1 <= i < j < k < l < m <= N 2. Ai < Aj < Ak < Al < Am
解法: 树状数组
思路: 可以参考以下这题的解法: http://www.cppblog.com/menjitianya/archive/2011/04/06/143510.html 那一题求得是非递减数列的数量,没有要求元素个数,这题是要求元素个数一定要 是5个,我们还是可以写出状态转移方程: dp[i][j] = sum{ dp[i-1][k], k<j, a[k] < a[j] } dp[i][j]表示长度为i以j结尾的 序列的数量,这题需要建立5个树状数组,sum这一步操作就可以通过树状数组的成段求 和来做。每次求i-1的满足情况的解,完毕后就将答案插入到i的树状数组中。 当长度为5的时候就是最后的答案了,累加即可。 */ #include <iostream> #include <algorithm> using namespace std;
typedef int hugeint; const int Base = 10000; const int Capacity = 7;
struct xnum { int Len; int Data[Capacity]; xnum() : Len(0) {} xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } xnum(char S[]); xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } void print(){ printf("%d",Len==0?0:Data[Len-1]); for(int i=Len-2;i>=0;i--) for(int j=Base/10;j>0;j/=10) printf("%d",Data[i]/j%10); } };
xnum::xnum(char S[]) { int I, J; Data[Len = 0] = 0; J = 1; for (I = strlen(S)-1; I>=0; I--) { Data[Len] += (S[I] - '0') * J; J *= 10; if (J >= Base) J = 1, Data[++Len] = 0; } if (Data[Len] > 0) Len++; }
int compare(const xnum& A, const xnum& B) { int I; if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); if (I < 0) return 0; return A[I] > B[I] ? 1 : -1; }
xnum operator+(const xnum& A, const xnum& B) { xnum R; int I; int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; Carry /= Base; } R.Len = I; return R; }
xnum operator-(const xnum& A, const xnum& B) { xnum R; int Carry = 0; R.Len = A.Len; int I; for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }
xnum operator*(const xnum& A, const int B) { int I; if (B == 0) return 0; xnum R; hugeint Carry = 0; for (I = 0; I < A.Len || Carry > 0; I++) { if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; Carry /= Base; } R.Len = I; return R; }
xnum operator*(const xnum& A, const xnum& B) { int I; if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) { hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; if (I + J < R.Len) Carry += R[I + J]; if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; Carry /= Base; } } return R; }
xnum operator/(const xnum& A, const int B) { xnum R; int I; hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) { C = C * Base + A[I]; R[I] = C / B; C %= B; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }
xnum operator/(const xnum& A, const xnum& B) { int I; xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } R[I] = Left; Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }
xnum operator%(const xnum& A, const xnum& B) { int I; xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; Left = 0; Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; } R[I] = Left; Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; }
istream& operator>>(istream& In, xnum& V) { char Ch; for (V = 0; In >> Ch;) { V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } return In; }
ostream& operator<<(ostream& Out, const xnum& V) { int I; Out << (V.Len == 0 ? 0 : V[V.Len - 1]); for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; return Out; }
xnum gcd(xnum a,xnum b) { if(compare(b,0)==0) return a; else return gcd(b,a%b); }
int div(char *A,int B) { int I; int C = 0; int Alen=strlen(A); for (I = 0; I <Alen; I++) { C = C * Base + A[I]-'0'; C %= B; } return C; }
#define maxn 50010
int n; xnum c[6][maxn]; int val[maxn], bin[maxn], tot;
int lowbit(int x) { return x & (-x); }
void add(int idx, int pos, xnum v) { while(pos <= n) { c[idx][pos] = c[idx][pos] + v; pos += lowbit(pos); } }
xnum sum(int idx, int pos) { xnum s = 0; while(pos > 0) { s = s + c[idx][pos]; pos -= lowbit(pos); } return s; }
int Bin(int v) { int l = 1; int r = tot; while(l <= r) { int m = (l + r) >> 1; if(bin[m] == v) return m; if(v > bin[m]) { l = m + 1; }else r = m - 1; } }
int main() { int i, j; while(scanf("%d", &n) != EOF) { tot = 0; for(i = 1; i <= n; i++) { scanf("%d", &val[i]); bin[i] = val[i]; } sort(bin+1, bin+1+n); for(i = 1; i <= n; i++) { if(i==1 || bin[i] != bin[i-1]) bin[ ++tot ] = bin[i]; } for(i = 0; i <= 5; i++) { for(j = 1; j <= n; j++) c[i][j] = 0; }
for(i = 1; i <= n; i++) { val[i] = Bin(val[i]); } xnum ans = 0; for(i = 1; i <= n; i++) { add(1, val[i], 1); for(j = 2; j <= 5; j++) { xnum p = sum(j-1, val[i]-1); if(p.Len) add(j, val[i], p);
if(j == 5) { ans = ans + p; } } } ans.print(); puts(""); } return 0; }
|