二更，蓝桥杯国赛来了这题，但是没做出来，重新理解了一遍
dpi：以第i小的字符结尾的上升子序列的种类数，dp从字符串头到尾遍历，
字符串中有若干个字符c，如(...c_1...c_2)，靠后面出现的字符(c_2)必定包含了前面同一字符(c_1)的所有可能，(c_2)也有自己独特的可能情况，如(c_1)和(c_2)间出现了比c小的其他字符等等，所以，最后答案就只用字符c最后一次出现的位置，该字符的贡献，所以加一个遇到的c字符的贡献，记录下来，之后再次出现时减去上一次的贡献再加上这次的贡献，这样就只记录了c字符最后一个的值，不过中间的值可以被其他字符使用到，所以要记录。
P3970 [TJOI2014]上升子序列
题目描述
给定一个只包含整数的序列(序列元素的绝对值大小不超过10^9),你需要计算上升子序列的个数,满足如下条件的称之为一个上升子序列:
-
是原序列的一个子序列
-
长度至少为2
-
所有元素都严格递增
如果两个上升子序列相同,那么只需要计算一次。例如:序列{1,2,3,3}有4个上升子序列,分别为{1,2}{1,3},{1,2,3},{2,3}
输入格式
输入的第一行是一个整数n,表示序列长度。接下来一行是n个整数,表示序列。
输出格式
输出仅包含一行,即原序列有多少个上升子序列。由于答案可能非常大,你只需要输出答案模10^9+7的余数。
输入
4
1 2 3 3
输出
4
数据范围
对于 30% 的数据，N ≤ 5000
对于 100% 的数据，N ≤ 10^5
如果不去重的话，dp[i]代表以第i小为结尾的上升子序列数量，(dp[i]=1+sum_{j=1}^{i-1}dp[j]) ，其中1是以a[i]作为为序列的数量，所以，用树状数组很容易维护这个前缀和。
当然，这样还有重复，但不能直接除去重复的元素，当某元素第二次出现时，当前元素dp[b]中包括了第一次出现该元素时dp[a]里的所有可能情况，所以减去重复的元素，也就是加上dp[b]中独有的方案数，还有就是长度为1的序列不能包括，但是我们去重的时候如果x出现了k次，那么x元素长度为1的情况已经只被记录过一次,即最后答案中长度为1的元素个数=去重之后的元素个数。
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
const int inf=0x3f3f3f3f,mod=1e9+7,MAXN=1e5+4;
int a[MAXN],aa[MAXN],tot,n;
int last[MAXN];
unordered_map<int,int>mp;
int num[MAXN];
inline int query(int pos){
int ans=0;
while(pos){
ans=(1ll*ans+num[pos])%mod;
pos-=lowbit(pos);
}
return ans;
}
inline void add(int pos,int val){
while(pos<=tot){
num[pos]=(1ll*num[pos]+val)%mod;
pos+=lowbit(pos);
}
}
int main() {
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",a+i);
aa[i]=a[i];
}
sort(aa,aa+n);
for(int i=0;i<n;++i)
if(!mp.count(aa[i]))mp.insert({aa[i],++tot});//离散化
for(int i=0;i<n;++i){
int pos=mp[a[i]];
int val=query(pos-1);
val=(val+1)%mod;//+1
add(pos,(1ll*val-last[pos]+mod)%mod);
last[pos]=val;
}
printf("%d",(int)(1ll*query(mp.size())-mp.size()+mod)%mod);
return 0;
}
HDU-3030
Problem Description
You were driving along a highway when you got caught by the road police for speeding. It turns out that they've been following you, and they were amazed by the fact that you were accelerating the whole time without using the brakes! And now you desperately need an excuse to explain that.
You've decided that it would be reasonable to say "all the speed limit signs I saw were in increasing order, that's why I've been accelerating". The police officer laughs in reply, and tells you all the signs that are placed along the segment of highway you drove, and says that's unlikely that you were so lucky just to see some part of these signs that were in increasing order.
Now you need to estimate that likelihood, or, in other words, find out how many different subsequences of the given sequence are strictly increasing. The empty subsequence does not count since that would imply you didn't look at any speed limits signs at all!
For example, (1, 2, 5) is an increasing subsequence of (1, 4, 2, 3, 5, 5), and we count it twice because there are two ways to select (1, 2, 5) from the list.
Input
The first line of input gives the number of cases, N. N test cases follow. The first line of each case contains n, m, X, Y and Z each separated by a space. n will be the length of the sequence of speed limits. m will be the length of the generating array A. The next m lines will contain the m elements of A, one integer per line (from A[0] to A[m-1]).
Using A, X, Y and Z, the following pseudocode will print the speed limit sequence in order. mod indicates the remainder operation.
for i = 0 to n-1
print A[i mod m]
A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z
Note: The way that the input is generated has nothing to do with the intended solution and exists solely to keep the size of the input files low.
1 ≤ m ≤ n ≤ 500 000
Output
For each test case you should output one line containing "Case #T: S" (quotes for clarity) where T is the number of the test case and S is the number of non-empty increasing subsequences mod 1 000 000 007.
Sample Input
2
5 5 0 0 5
1
2
1
2
3
6 2 2 1000000000 6
1
2
Sample Output
Case #1: 15
Case #2: 13
AXYZ感觉就是多余的，题目为啥不把直接把结果给出来。
题目理解了就是模板了，啥都不用除去。
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define Init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f,mod=1e9+7,MAXN=5e5+4,MAXM=2e1+8;
typedef long long ll;
int a[MAXN],aa[MAXN],tot;
int A[MAXN];
int n,m,X,Y,Z;
unordered_map<int,int>mp;
int num[MAXN];
inline int query(int pos){
int ans=0;
while(pos){
ans=(1ll*ans+num[pos])%mod;
pos-=lowbit(pos);
}
return ans;
}
inline void add(int pos,int val){
while(pos<=tot){
num[pos]=(1ll*num[pos]+val)%mod;
pos+=lowbit(pos);
}
}
int main() {
#ifdef LOCAL_LY
freopen("in.txt","r",stdin);
#endif
int t,cas=1;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d%d",&n,&m,&X,&Y,&Z);
for(int i=0;i<m;++i){
scanf("%d",A+i);
}
for(int i=0;i<n;++i){
aa[i]=a[i]=A[i%m];
A[i%m]=(1ll*X*A[i%m]%Z+1ll*Y*(i+1)%Z)%Z;
}
sort(aa,aa+n);
mp.clear();
Init(num,0);
tot=0;
for(int i=0;i<n;++i)
if(!mp.count(aa[i]))mp.insert({aa[i],++tot});
for(int i=0;i<n;++i){
int pos=mp[a[i]];
int val=(query(pos-1)+1)%mod;
add(pos,val);
}
printf("Case #%d: %d
",cas++,query(mp.size()));
}
return 0;
}
未完待续...