本文共 1479 字，大约阅读时间需要 4 分钟。
该题题义就是给定一个长度为M的A数组，依照这个数组生成一个长度为N的数组，然后求严格增长的子串个数。
对于所给定的值进行离散化排序，再巧用树状数组求个数。
代码如下：
#include #include #include #include #include #define MOD 1000000007 #define MAXN 500005 using namespace std; int num[MAXN], A[MAXN], c[MAXN], seq[MAXN], cnt; inline int lowbit(int x) { return x & -x; } inline void modify(int pos, int val) { for (int i = pos; i <= cnt; i += lowbit(i)) { c[i] += val; if (c[i] >= MOD) c[i] %= MOD; } } inline int getsum(int pos) { int s = 0; for (int i = pos; i > 0; i -= lowbit(i)) { s += c[i]; if (s >= MOD) s %= MOD; } return s; } int main() { int T, n, m; long long X, Y, Z, res; scanf("%d", &T); for (int ca = 1; ca <= T; ++ca) { res = 0; map mp; scanf("%d %d %I64d %I64d %I64d", &n, &m, &X, &Y, &Z); memset(c, 0, sizeof (c)); for (int i = 0; i < m; ++i) { scanf("%d", &A[i]); } for (int i = 0; i < n; ++i) { num[i+1] = A[i%m]; seq[i] = num[i+1]; A[i%m] = (X*A[i%m]+Y*(i+1))%Z; } sort(num+1, num+1+n); cnt = unique(num+1, num+1+n) - (num+1); for (int i = 1; i <= cnt; ++i) { mp[num[i]] = i; } modify(1, 1); for (int i = 0; i < n; ++i) { long long x = getsum(mp[seq[i]]); res += x; if (res > MOD) res %= MOD; modify(mp[seq[i]]+1, x); } printf("Case #%d: %I64d\n", ca, res); } return 0; }
转载于:https://www.cnblogs.com/Lyush/archive/2012/02/26/2369036.html