showproblem.php?pid=4901

每一步都要mod，浪费了220分钟。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define mt(a,b) memset(a,b,sizeof(a))
 4 typedef __int64 LL;
 5 const int mod=1000000007;
 6 const int M=1024;
 7 int a[M];
 8 LL dpxor[M][M],dpand[M][M];
 9 int main(){
10     int t,n;
11     while(~scanf("%d",&t)){
12         while(t--){
13             scanf("%d",&n);
14             for(int i=1;i<=n;i++){
15                 scanf("%d",&a[i]);
16             }
17             mt(dpxor,0);
18             mt(dpand,0);
19             for(int i=1;i<=n;i++){
20                 dpxor[i][a[i]]=1;
21                 for(int j=0;j<M;j++){
22                     dpxor[i][j^a[i]]+=dpxor[i-1][j];
23                     dpxor[i][j^a[i]]%=mod;
24                     dpxor[i][j]+=dpxor[i-1][j];
25                     dpxor[i][j]%=mod;
26                 }
27             }
28             for(int i=n;i>=1;i--){
29                 dpand[i][a[i]]=1;
30                 for(int j=0;j<M;j++){
31                     dpand[i][j&a[i]]+=dpand[i+1][j];
32                     dpand[i][j&a[i]]%=mod;
33                     dpand[i][j]+=dpand[i+1][j];
34                     dpand[i][j]%=mod;
35                 }
36             }
37             LL ans=0;
38             for(int i=1;i<=n;i++){
39                 for(int j=0;j<M;j++){
40                     ans+=((dpxor[i][j]+mod-dpxor[i-1][j])%mod)*dpand[i+1][j];
41                     ans%=mod;
42                 }
43             }
44             printf("%I64d
",ans);
45         }
46     }
47     return 0;
48 }

View Code

Nice boat http://acm.hdu.edu.cn/showproblem.php?pid=4902

竟然pe，逗比。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define lrrt int L,int R,int rt
  4 #define iall 1,n,1
  5 #define imid int mid=(L+R)>>1
  6 #define lson L,mid,rt<<1
  7 #define rson mid+1,R,rt<<1|1
  8 using namespace std;
  9 const int M=100010;
 10 int a[M];
 11 struct T{
 12     int big,cover;
 13 }tree[M<<2];
 14 void pushup(int rt){
 15     tree[rt].big=max(tree[rt<<1].big,tree[rt<<1|1].big);
 16     tree[rt].cover=(tree[rt<<1].cover==tree[rt<<1|1].cover)?tree[rt<<1].cover:-1;
 17 }
 18 void build(lrrt){
 19     if(L==R){
 20         tree[rt].big=tree[rt].cover=a[L];
 21         return ;
 22     }
 23     imid;
 24     build(lson);
 25     build(rson);
 26     pushup(rt);
 27 }
 28 void pushdown(int rt){
 29     if(~tree[rt].cover){
 30         tree[rt<<1].big=tree[rt<<1].cover=tree[rt<<1|1].big=tree[rt<<1|1].cover=tree[rt].cover;
 31     }
 32 }
 33 void update(int x,int y,int val,lrrt){
 34     if(x<=L&&R<=y){
 35         tree[rt].big=tree[rt].cover=val;
 36         return ;
 37     }
 38     pushdown(rt);
 39     imid;
 40     if(mid>=x) update(x,y,val,lson);
 41     if(mid<y)  update(x,y,val,rson);
 42     pushup(rt);
 43 }
 44 int gcd(int a,int b){
 45     return b?gcd(b,a%b):a;
 46 }
 47 void change(int x,int y,int val,lrrt){
 48     if(L==R){
 49         if(tree[rt].big<=val) return ;
 50         int now=gcd(tree[rt].cover,val);
 51         tree[rt].cover=tree[rt].big=now;
 52         return ;
 53     }
 54     imid;
 55     if(x<=L&&R<=y){
 56         if(tree[rt].big<=val) return ;
 57         if(~tree[rt].cover){
 58             if(tree[rt].cover<=val) return ;
 59             int now=gcd(tree[rt].cover,val);
 60             tree[rt].cover=tree[rt].big=now;
 61             return ;
 62         }
 63         pushdown(rt);
 64         change(x,y,val,lson);
 65         change(x,y,val,rson);
 66         pushup(rt);
 67         return ;
 68     }
 69     pushdown(rt);
 70     if(mid>=x) change(x,y,val,lson);
 71     if(mid<y)  change(x,y,val,rson);
 72     pushup(rt);
 73 }
 74 void query(lrrt){
 75     if(L==R){
 76         printf("%d ",tree[rt].big);
 77         return ;
 78     }
 79     pushdown(rt);
 80     imid;
 81     query(lson);
 82     query(rson);
 83 }
 84 int main(){
 85     int t,n,m;
 86     while(~scanf("%d",&t)){
 87         while(t--){
 88             scanf("%d",&n);
 89             for(int i=1;i<=n;i++){
 90                 scanf("%d",&a[i]);
 91             }
 92             build(iall);
 93             scanf("%d",&m);
 94             while(m--){
 95                 int op,l,r,x;
 96                 scanf("%d%d%d%d",&op,&l,&r,&x);
 97                 if(op&1) update(l,r,x,iall);
 98                 else     change(l,r,x,iall);
 99             }
100             query(iall);
101             puts("");
102         }
103     }
104     return 0;
105 }

View Code

end