2017 ACM/ICPC Asia Regional Xi'an Online

unsolved

分别加减得到的二次项系数做差即可剩余偶数项

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const LL mod=1e9+7;
 6 
 7 LL pow_mod(LL a,LL n){
 8     long long res=1,t=a;
 9     while(n){
10         if(n&1) res=(res*t)%mod;
11         n/=2;
12         t=(t*t)%mod;
13     }
14     return res;
15 }
16 
17 int main(){
18     LL t;
19     scanf("%lld",&t);
20     while(t--){
21         LL p,q,k;
22         scanf("%lld%lld%lld",&p,&q,&k);
23         LL x=(2*q-p);
24         x=(x%mod+mod)%mod;
25         x=(LL)(pow_mod(x,k)*pow_mod(pow_mod(p,k),mod-2))%mod;
26         if(k%2==0) x++;
27         else x=1-x;
28         x=(x%mod+mod)%mod;
29         x=(LL)x*pow_mod(2,mod-2)%mod;
30         printf("%lld
",x);
31     }
32 
33 
34     return 0;
35 }

Psong

C Sum

输出233个10000000

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int main(){
 5     int t;
 6     scanf("%d",&t);
 7     while(t--){
 8         int x;
 9         scanf("%d",&x);
10         for(int i=1;i<=233;i++){
11             printf("10000000");
12         }
13         printf("
");
14     }
15 
16     return 0;
17 }

Psong

D Brain-baffling Game

unsolved

E Maximum Flow

每个数的贡献为min（x，x ^（n-1）），暴力找0和1出现的规律。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const LL mod=1e9+7;
 6 
 7 LL ans1,ans2;
 8 
 9 LL fun(LL x){
10     LL cnt=0;
11     while(x){
12         x/=2;
13         cnt++;
14     }
15     return cnt-1;
16 }
17 
18 LL p[65];
19 
20 int main(){
21     p[0]=1;
22     for(LL i=1;i<65;i++) p[i]=p[i-1]*2%mod;
23     LL n;
24     while(scanf("%lld",&n)!=EOF){
25         n--;
26         LL tttt=n;
27         ans1=ans2=0;
28         LL cnt=fun(n);
29         LL tmp=(1LL<<cnt)-1;
30         tmp%=mod;
31         ans1=(tmp*(tmp+1)/2)%mod;
32 
33         n=n^(1LL<<cnt);
34         LL res=0;
35         for(LL i=0;i<=cnt;i++){
36             LL num=0;
37             res+=p[i]*((n&(1LL<<i))?1:0);
38             res%=mod;
39             num+=(n>>(i+1))*p[i]%mod;
40             if(n&(1LL<<i)) num+=res-p[i]+1;
41             if(n&(1LL<<i)) ans2+=((n-num+1)%mod+mod)*p[i]%mod;
42             else ans2+=(num%mod)*p[i]%mod;
43             ans2%=mod;
44         }
45         LL ans=(ans1+ans2+tttt)%mod;
46         printf("%lld
",ans);
47     }
48 
49     return 0;
50 }

Psong

F Trig Function

好像有公式。

G Xor

Big-Small

1.对于小数据，预处理出每个点向上跳，跳到根，步伐为k的结果。

2.对于大数据，两个端点都倍增得向上跳到lca。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int MAX_V=5e4+5;
  5 const int MAX_LOG=18;
  6 int S;
  7 
  8 int n,q;
  9 int a[MAX_V];
 10 
 11 vector<int> g[MAX_V];
 12 int fa[MAX_LOG][MAX_V];
 13 int depth[MAX_V];
 14 void addedge(int u,int v){
 15     g[u].push_back(v);
 16     g[v].push_back(u);
 17 }
 18 void dfs(int u,int pre,int d){
 19     fa[0][u]=pre;
 20     depth[u]=d;
 21     for(int i=0;i<g[u].size();i++){
 22         int v=g[u][i];
 23         if(v==pre) continue;
 24         dfs(v,u,d+1);
 25     }
 26 }
 27 void init(int n){
 28     depth[0]=0;
 29     dfs(1,0,1);
 30     for(int k=0;k+1<MAX_LOG;k++){
 31         fa[k+1][0]=fa[k][0]=0;
 32         for(int v=1;v<=n;v++){
 33             fa[k+1][v]=fa[k][fa[k][v]];
 34         }
 35     }
 36 }
 37 int LCA(int u,int v){
 38     if(depth[u]>depth[v]) swap(u,v);
 39     for(int k=MAX_LOG-1;k>=0;k--){
 40         if((depth[v]-depth[u])&(1<<k)){
 41             v=fa[k][v];
 42         }
 43     }
 44     if(u==v) return u;
 45     for(int k=MAX_LOG-1;k>=0;k--){
 46         if(fa[k][u]!=fa[k][v]){
 47             u=fa[k][u];
 48             v=fa[k][v];
 49         }
 50     }
 51     return fa[0][v];
 52 }
 53 
 54 int id[MAX_V];
 55 int dp[MAX_V][605];
 56 int par[MAX_V][605];
 57 void dfs2(int u,int d){
 58     id[d]=u;
 59     par[u][0]=u;
 60     for(int i=1;i<=S;i++){
 61         dp[0][i]=0;
 62         if(d<=i){
 63             dp[u][i]=a[u];
 64             par[u][i]=0;
 65         }
 66         else {
 67             dp[u][i]=a[u]^dp[id[d-i]][i];
 68             par[u][i]=id[d-i];
 69         }
 70     }
 71     for(int i=0;i<g[u].size();i++){
 72         int v=g[u][i];
 73         if(v==fa[0][u]) continue;
 74         dfs2(v,d+1);
 75     }
 76 }
 77 
 78 int pre(int u,int k){
 79     int res=u;
 80     for(int i=MAX_LOG-1;i>=0;i--){
 81         if(k&(1<<i)) res=fa[i][res];
 82     }
 83     return res;
 84 }
 85 
 86 int solve1(int u,int v,int k){
 87     int lca=LCA(u,v);
 88     int res=(depth[v]+depth[u]-2*depth[lca])%k;
 89     int s=u,t=pre(v,res);
 90     int ans=0;
 91     if((depth[u]-depth[lca])%k==0) ans=a[lca];
 92     while(depth[s]>depth[lca]){
 93         ans^=a[s];
 94         s=pre(s,k);
 95     }
 96     while(depth[t]>depth[lca]){
 97         ans^=a[t];
 98         t=pre(t,k);
 99     }
100     return ans;
101 }
102 int solve2(int u,int v,int k){
103     int lca=LCA(u,v);
104     int res1=(k-((depth[u]-depth[lca])%k))%k;
105     int s1=u,s2=par[lca][res1];
106 
107     int ans=dp[s1][k]^dp[s2][k];
108     if((depth[u]-depth[lca])%k==0) ans^=a[lca];
109 
110     int res2=(depth[v]+depth[u]-2*depth[lca])%k;
111     int t1=par[v][res2];
112     if(lca!=v&&depth[t1]>depth[lca]){
113         int res3=(k-((depth[t1]-depth[lca])%k))%k;
114         int t2=par[lca][res3];
115         ans^=(dp[t1][k]^dp[t2][k]);
116     }
117 
118     return ans;
119 }
120 
121 int main(){
122     while(~scanf("%d%d",&n,&q)){
123         S=min(600,(int)sqrt(q*(log(1.0*n)/log(2.0))));
124         for(int i=1;i<=n;i++){
125             g[i].clear();
126         }
127         for(int i=1;i<n;i++){
128             int u,v;
129             scanf("%d%d",&u,&v);
130             addedge(u,v);
131         }
132         for(int i=1;i<=n;i++){
133             scanf("%d",&a[i]);
134         }
135         init(n); dfs2(1,1);
136         while(q--){
137             int u,v,k;
138             scanf("%d%d%d",&u,&v,&k);
139             if(k>S) printf("%d
",solve1(u,v,k));
140             else printf("%d
",solve2(u,v,k));
141         }
142     }
143 
144     return 0;
145 }

Psong

H Music

unsolved

I Barty's Computer

unsolved

J Easy Problem

unsolved