本文主要是介绍NOIP-模拟试题之--序列问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2018 NOIP 全套资料下载
【题目描述】
小H是个善于思考的学生,她正在思考一个有关序列的问题。
她的面前浮现出了一个长度为n的序列{ai},她想找出两个非空的集合S、T。
这两个集合要满足以下的条件:
-
两个集合中的元素都为整数,且都在 [1, n] 里,即Si,Ti ∈ [1, n]。
-
对于集合S中任意一个元素x,集合T中任意一个元素y,满足x < y。
-
对于大小分别为p, q的集合S与T,满足
a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2] and a[t3] ... and a[tq].
小H想知道一共有多少对这样的集合(S,T),你能帮助她吗?
【输入格式】
第一行,一个整数n
第二行,n个整数,代表ai。
【输出格式】
仅一行,表示最后的答案。
【样例输入】
4
1 2 3 3
【样例输出】
4
【样例解释】
S = {1,2}, T = {3}, 1 ^ 2 = 3 = 3 (^为异或)
S = {1,2}, T = {4}, 1 ^ 2 = 3 = 3
S = {1,2}, T = {3,4} 1 ^ 2 = 3 & 3 = 3 (&为与运算)
S = {3}, T = {4} 3 = 3 = 3
【数据范围】
30%: 1 <= n <= 10
60%: 1 <= n <= 100
100%: 1 <= n <= 1000, 0 <= ai < 1024
/*
枚举集合不说了
其实这题需要高精的…
维护i到n &值为j的方案数
维护1到i ^值为j的方案数
然后枚举断点 乘起来
*/
#include< iostream>
#include< cstdio>
#include< cstring>
#define maxn 2050
#define ll long long
using namespace std;
ll n,a[maxn],b[maxn],sum[maxn],f[maxn][maxn+200],g[maxn][maxn+200],ans;
int main()
{
freopen(“sequence.in”,“r”,stdin);
freopen(“sequence.out”,“w”,stdout);
cin>>n;
for(ll i=1;i<=n;i++)
cin>>a[i];
for(ll i=1;i<=n;i++)
b[i]=a[n-i+1];
for(ll i=1;i<=n;i++){
for(ll j=0;j<=2048;j++)
f[i][j]=sum[j^a[i]];
f[i][a[i]]++;
for(ll j=0;j<=2048;j++)
sum[j]+=f[i][j];
}
memset(sum,0,sizeof(sum));
for(ll i=0;i<n;i++){
for(ll j=0;j<=2048;j++)
g[i+1][j&b[i+1]]+=sum[j];
g[i+1][b[i+1]]++;
for(ll j=0;j<=2048;j++)
sum[j]+=g[i+1][j];
}
memset(sum,0,sizeof(sum));
for(ll i=1;i<n;i++){
for(ll j=0;j<2048;j++)
sum[j]+=f[i][j];
for(ll j=0;j<2048;j++)
ans+=sum[j]*g[n-i][j];
}
cout<<ans;
return 0;
}
这篇关于NOIP-模拟试题之--序列问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!