南阳理工学院ACM团队0787号竞赛:计算子序列的数量
子序列个数
1000 ms | 内存限制: 65535
3
子序列的定义:对于一个序列a=a[1],a[2],......a[n],则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列,其中1<=p1<p2<.....<pm<=n。 例如:4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。
对于给出序列a,有些子序列可能是相同的,这里只算做1个,要求输出a的不同子序列的数量。
输入包含多组数据(不超过100组)
每组数据有两行:
第一行:整数n(1<=n<=100),代表数组元素个数
第二行:n个整数a[i](0<=a[i]<=110 ),代表数组元素
输出
每组输出单独占一行。
输出子序列的个数对1000000007取余数的结果。
样例输入
5 1 92 69 52 67 2 1 2
样例输出
31 3
题目程序不难写,主要是推导数学公式比较难,按照递推,该题有如下关系:
设f(k)为长度为k的序列的子序列个数,则很显然以下推论成立:
1.当a[k]和前面的数都不相同的时候,f(k)的个数包含f(k-1)的个数,然后把f(k-1)的每个序列和a[k]组合起来,得到的新序列也是f(k)的子序列,那么则有以下关系:
f(k) = 2 * f(k - 1) + 1
2.如果a[k]在前面的数中出现过的话,则f(k)的个数除了上面的还要减去最近一次出现a[k]这个数值的地方-1的子序列个数,+1也没有了,因为f(a[k]上次出现的位置)包括了a[k]单独算一次的情况,由此可推出关系式如下:
f(k) = 2 * f(k - 1) - f(a[k]上次出现的位置 - 1)
有了这两个递推表达式,这就有一个完整的递推关系了,代码写起来比较简单,AC代码如下:
#include<iostream>
#include<string.h>
#define MAX 115
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int main()
{
ll n,a[MAX],f[MAX],vis[MAX];
while(cin >> n)
{
for(int i = 1;i <= n; i++)
cin >> a[i];
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
f[1] = 1;
vis[a[1]] = 1;
for(int i = 2;i <= n; i++)
{
if(vis[a[i]] == 0)
f[i] = (f[i - 1] * 2 + 1) % mod;
else
f[i] = (f[i - 1] * 2 - f[vis[a[i]] - 1]) % mod;
vis[a[i]] = i;
}
cout << f[n] << endl;
}
return 0;
}