一点都不良心！！！！
AK 快乐
爆零快乐！！！
1、
A、 value
512mb 1s
规定一个区间的价值为这个区间中所有数 and 起来的值与这个区间所有数 or 起
来的值的乘积。
例如 3 个数 2,3,6。它们 and 起来的值为 2， or 起来的值为 7，这个区间对答
案的贡献为 2*7=14。
现在有一个 n 个数的序列， 想知道所有 n*(n+1)/2 个区间的贡献的和对
1000000007 取模后的结果是多少。
例如当这个序列为{3,4,5}时，那么区间[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]的贡献
分别为 9,0,0,16,20,25。
Input
第一行一个数 n
接下来一行 n 个数 ai，表示这 n 个数(0<=ai<=10^9)。
Output
一行表示答案。
Input
3
4 5
Output
70
limit
%30 n<=1000
%100 n<=100000
我打的是nlog^2 拆位树状数组维护，f[i]表示区间i~现在循环到的点，的&值，g[i]表示|值。
然后记录最后连续有多少个1或者0，然后区间修改f和g。。
【慢且错 不说话。。
正解是，不用拆位，也是维护f,g,然后当前f和g的不同的值只有logn个，并且是单调的，然后说可以用链表？[我觉得是单调队列啊ORZ。。
这样就nlogn了。。。
要不要放我的垃圾代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100010
#define Mod 1000000007
#define LL long long LL a[Maxn];
LL f[][Maxn],g[][Maxn];
LL ct[],lt[];
LL n; void add(LL x,LL l,LL r,LL c)
{
if(l>r) return;
c%=Mod;
// printf("%lld %lld %lld %lld\n",x,l,r,c);
for(LL i=l;i<=n;i+=i&(-i))
f[x][i]=(f[x][i]+c)%Mod,g[x][i]=(g[x][i]+l*c)%Mod;
r++;
for(LL i=r;i<=n;i+=i&(-i))
f[x][i]=(f[x][i]+Mod-c)%Mod,g[x][i]=(g[x][i]+Mod-(r*c)%Mod)%Mod;
} LL gsum(LL x,LL l,LL r)
{
if(l>r) return ;
// printf("ask:%lld %lld %lld ",x,l,r);
LL ans=;
for(LL i=r;i>=;i-=i&(-i))
ans=(ans+(r+)*f[x][i]-g[x][i])%Mod;
l--;
for(LL i=l;i>=;i-=i&(-i))
ans=(ans-(l+)*f[x][i]+g[x][i])%Mod;
// printf("%lld\n",ans);
ans=(ans%Mod+Mod)%Mod;
return ans;
} int main()
{
LL ans=;
scanf("%lld",&n);
for(LL i=;i<=n;i++) scanf("%lld",&a[i]);
memset(f,,sizeof(f));
memset(g,,sizeof(g));
for(LL i=;i<=;i++) lt[i]=-,ct[i]=n+;
LL sum=;
for(LL i=;i<=n;i++)
{
for(LL j=;j<=;j++)
{
LL y=a[i]&(1LL<<j-);
if(y==)
{
if(lt[j]!=)
{
sum=sum-((1LL<<j-)*gsum(,ct[j],i-))%Mod;
sum=(sum%Mod+Mod)%Mod;
// printf("sum=%lld\n",sum);
// add(2,ct[j],i-1,-(1LL<<j-1)*gsum(1,ct[j],i-1));
add(,ct[j],i-,-(1LL<<j-));
lt[j]=;ct[j]=i;
}
}
else
{
if(lt[j]!=)
{ sum=sum+((1LL<<j-)*gsum(,ct[j],i-))%Mod;
sum=(sum%Mod+Mod)%Mod;
// printf("sum=%lld\n",sum);
// add(2,ct[j],i-1,(1LL<<j-1)*gsum(0,ct[j],i-1));
add(,ct[j],i-,(1LL<<j-));
lt[j]=;ct[j]=i;
}
}
}
add(,i,i,a[i]);add(,i,i,a[i]);
sum=(sum+a[i]*a[i])%Mod;
//add(2,i,i,(a[i]*a[i])%Mod);
ans=(ans+sum)%Mod;
// printf("sum=%lld\n",sum);
// ans=(ans+gsum(2,1,i))%Mod;
// printf("ans=%lld\n",ans);
ans=(ans%Mod+Mod)%Mod;
}
printf("%lld\n",ans);
return ;
}
真的好丑的code的说。。
2、
Sample Input
3 50
Sample Output
2
数位DP，数位DP，我打的数位DP太垃圾了，，又慢有错ORZ。。
不会告诉你我现在还没调出来，放弃治疗。。。
大数据还是错，应该是中间爆了吧ORZ。。。
233经过GDXB提点，终于AC了。。。。qpow爆了ORZ。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
// #define Mod 1000000007
#define LL long long const LL Mod= ; LL n,p;
LL f[][][],g[][][];
LL get_ans1(int x,int fl1,int fl2)
{
if(x==) return ;
LL ans=;
LL y=(n&(1LL<<x-));
if(y!=) y=;
// if(!fl1&&!fl2&&f[x]!=-1) return f[x];
if(f[x][fl1][fl2]!=-) return f[x][fl1][fl2];
LL add=(1LL<<x-)%Mod,ad1=(n&((1LL<<x-)-))+;
if(y==)
{
ans=(ans+get_ans1(x-,,fl2)+add*add)%Mod; //0 -> 1
if(fl1) add=ad1;
add%=Mod;
ans=(ans+get_ans1(x-,fl1,)+((1LL<<x-)%Mod)*add)%Mod;//1 -> 0
}
else //
{
if(!fl1) ans=(ans+get_ans1(x-,fl1,fl2)+add*add)%Mod; //1->0
if(fl1) add=(n&((1LL<<x-)-))+;
add%=Mod;
if(!fl2) ans=(ans+get_ans1(x-,fl1,fl2)+add*((1LL<<x-)%Mod))%Mod;//0->1
else ans=(ans+get_ans1(x-,fl1,fl2))%Mod;//0->0
}
f[x][fl1][fl2]=ans;
// if(!fl1&&!fl2) f[x]=ans;
return ans;
} LL qpow(LL x,LL b)
{
x%=Mod;
LL ans=;
while(b)
{
if(b&) ans=(ans*x)%Mod;
x=(x*x)%Mod;
b>>=;
}
return ans;
} LL get_ans2(int x,int fl1,int fl2)
{
if(x==) return ;
LL ans=;
LL y=(n&(1LL<<x-));
if(y!=) y=;
// if(!fl1&&!fl2&&g[x]!=-1) return g[x];
if(g[x][fl1][fl2]!=-) return g[x][fl1][fl2];
LL ad1=1LL<<x-,ad2=(n&((1LL<<x-)-))+,add=ad1;
ad1%=Mod;ad2%=Mod;add%=Mod;
if(y==)
{
if(fl2) add=ad2;add%=Mod;
ans=(ans+get_ans2(x-,,fl2)+((ad1*add)%Mod)*((1LL<<x-)%Mod))%Mod; //0 -> 1
ans=(ans+get_ans2(x-,,))%Mod; //0 -> 0
// if(fl1) add=(n&((1<<x-1)-1))+1;
add=ad1;
add%=Mod;
if(fl1) add=ad2;
add%=Mod;
ans=(ans+get_ans2(x-,fl1,)+((add*ad1)%Mod)*((1LL<<x-)%Mod))%Mod;//1 -> 0
ans=(ans+get_ans2(x-,fl1,fl2))%Mod;//1 -> 1
}
else //
{
if(!fl1)
{
if(!fl2) ans=(ans+get_ans2(x-,fl1,fl2))%Mod; //1->1
if(fl2) add=ad2;add%=Mod;
ans=(ans+get_ans2(x-,fl1,fl2)+((ad1*add)%Mod)*((1LL<<x-)%Mod))%Mod; //1->0
}
// if(fl1) add=(n&((1<<x-1)-1))+1;
add=ad1;
if(fl1) add=ad2;
add%=Mod;
if(!fl2) ans=(ans+get_ans2(x-,fl1,fl2)+((add*ad1)%Mod)*((1LL<<x-)%Mod))%Mod;//0->1
ans=(ans+get_ans2(x-,fl1,fl2))%Mod;//0->0
}
// if(!fl1&&!fl2) g[x]=ans;
ans%=Mod;
g[x][fl1][fl2]=ans;
return ans;
} int main()
{
int mx=;
scanf("%lld%lld",&n,&p);
LL now=n,d,dd;
while(now) mx++,now/=;
memset(f,-,sizeof(f));
n--;
LL a1=get_ans1(mx,,),ans=,a2;
// printf("---%lld\n",a1);
d=qpow(,Mod-);dd=qpow(n+,Mod-);
// ans=(ans+((a1*p)%Mod)*(qpow(100,Mod-2)*qpow(n,Mod-2))%Mod)%Mod;
a1=( ((d*p)%Mod)*((a1*dd)%Mod) )%Mod;
// printf("%lld\n",a1);
ans=(ans+a1)%Mod;
// printf("%lld\n",ans); memset(g,-,sizeof(g));
a2=get_ans2(mx,,);
// printf("---%lld\n",a2);
n++;
d=qpow(,Mod-);dd=qpow(((n%Mod)*(n%Mod))%Mod,Mod-);
// ans=(ans+(a2*(100-p)%Mod)*(qpow(100,Mod-2))*qpow(n*n,Mod-2)%Mod)%Mod;
a2=( ((d*(-p))%Mod)* ((a2*dd)%Mod) )%Mod;
ans=(ans+a2)%Mod; // ans=(ans%Mod+Mod)%Mod;
printf("%lld\n",ans);
return ;
}
无视我的调试真的好丑。。
3、
Sample Input
5 3
1 2
1 3
2 4
4 5
2 2
4 1
2 3
Sample Output
313
HINT
1<=P<=N
1<=K<=N
%30
N<=2000
Q<=2000
%100
N<=100000
Q<=100000
啊，可持久化。。。
就是先算b在a上面，这个直接算
然后就是b在c下面，那么就是a->b->c这条链
然后对于dis[a,c]>=k 那么b有k个位置
对于dis[a,c]<k 有dis[a,c]个位置
算出dfs序，然后就是询问区间小于等于k的东西的值
我打的是字母树。。。
啊啊啊数据开小了就 开心了！！真开心！！！
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 200010
#define Maxd 30 struct node
{
int x,y,next;
}t[Maxn*];int len;
int first[Maxn]; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} int dep[Maxn],sm[Maxn],dfn[Maxn],rt[Maxn],cnt=;
void dfs(int x,int f)
{
dfn[x]=++cnt;dep[dfn[x]]=dep[dfn[f]]+;
rt[dfn[x]]=dfn[x];sm[dfn[x]]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
dfs(y,x);
sm[dfn[x]]+=sm[dfn[y]];
rt[dfn[x]]=rt[dfn[y]];
}
} int rrt[Maxn];
struct hp
{
int lc,rc,ct,f;
}tr[Maxn*];
int tot=; void upd(int x)
{
tr[x].lc=tr[x].rc=tr[x].ct=;
} void build()
{
int lt;
tr[].lc=tr[].rc=tr[].ct=;
rrt[]=;
for(int i=;i<=cnt;i++)
{
lt=rrt[i-];
rrt[i]=++tot;
int now=rrt[i];
int z=dep[i];
for(int j=Maxd;j>=;j--)
{
int x=(z&(<<j-));
if(x!=) x=;
if(x==)
{
tr[now].lc=++tot;upd(tot);
tr[now].rc=tr[lt].rc;
lt=tr[lt].lc;
tr[tot].ct=tr[lt].ct+;
tr[tot].f=tr[lt].f+z;
now=tot;
}
else
{
tr[now].rc=++tot;upd(tot);
tr[now].lc=tr[lt].lc;
lt=tr[lt].rc;
tr[tot].ct=tr[lt].ct+;
tr[tot].f=tr[lt].f+z;
now=tot;
}
}
}
} int sum;
int query(int l,int r,int x)
{
sum=;int ans=;
l=rrt[l-],r=rrt[r];
for(int i=Maxd;i>=;i--)
{
int y=x&(<<i-);
if(y!=) y=;
if(y==)
{
r=tr[r].lc;
l=tr[l].lc;
}
else
{
sum+=tr[tr[r].lc].ct-tr[tr[l].lc].ct;
ans+=(tr[tr[r].lc].f-tr[tr[l].lc].f);
r=tr[r].rc;
l=tr[l].rc;
}
}
return ans;
} int main()
{
int n,q;
scanf("%d%d",&n,&q);
len=;
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dep[]=;
dfs(,);
build();
for(int i=;i<=q;i++)
{
int p,k,ans=;
scanf("%d%d",&p,&k);
if(dep[dfn[p]]->=k) ans+=k*(sm[dfn[p]]-);
else ans+=(dep[dfn[p]]-)*(sm[dfn[p]]-); ans+=query(dfn[p]+,rt[dfn[p]],k++dep[dfn[p]]);
ans+=k*(sm[dfn[p]]--sum)-dep[dfn[p]]*sum-sum; printf("%d\n",ans);
}
return ;
}
改数据范围就A了smg！！！
垃圾的人生！！！坎坷！！！
2016-11-06 17:33:10