【比赛链接】http://59.61.75.5:8018/contest/217
A. 异或
【题意】
已知一个序列 $a_{1dots n}$，定义 $f(x)$ 为小于等于 $x$ 的 $a_i$ 的数目。
$Q$ 次询问，每次给定 $l,r,x$，求 $sum_{i=l}^r f(ioplus x)^2$。
【数据范围】$1le n,Qle 10^5,0le a_i<2^{30},0le lle r < 2^{30},0le x<2^{30}$。
【题解】
考虑拆成 $sum_{i=0}^r f(ioplus x)^2 - sum_{i=0}^{l-1} f(ioplus x)^2$ 两部分进行求解。
根据异或的性质，$[0,r]$ 间的数在异或 $x$ 后应拆分为最多 $log$ 段，逐位拆分，每段分别计算。
考虑每段的答案仍然采用前缀和相减。二分查找对应的位置即可。细节详见代码。
效率 $O(n log^2 n)$。期望得分：100。
【代码】
1 #include<bits/stdc++.h> 2 const int mod=998244353; 3 const int maxn=100000+10; 4 int a[maxn],val[maxn],cnt[maxn],tot,n,Q; 5 long long sum[maxn]; 6 std::set<int> s; 7 std::map<int,int> map; 8 inline int ask ( int x ) 9 { 10 int pos=std::upper_bound(val+1,val+tot+1,x)-val-1; 11 return (!pos) ? 0 : (sum[pos-1]+1LL*(x-val[pos]+1)%mod*cnt[pos]%mod*cnt[pos]%mod)%mod; 12 } 13 inline int Ask ( int l,int r ) { return (ask(r)-ask(l-1)+mod)%mod; } 14 inline int query ( int p,int x ) 15 { 16 if ( p<0 ) return 0; 17 int u=0,ans=0; 18 for ( int i=30;~i;i-- ) 19 { 20 int k=(x>>i)&1; 21 if ( (p>>i)&1 ) ans=(ans+Ask(u|(k<<i),(u|(k<<i))+(1<<i)-1))%mod,u+=(k^1)<<i; 22 else u|=k<<i; 23 } 24 return (ans+Ask(u,u))%mod; 25 } 26 signed main() 27 { 28 scanf("%d%d",&n,&Q); 29 for ( int i=1;i<=n;i++ ) scanf("%d",&a[i]),s.insert(a[i]); 30 for ( int x:s ) val[map[x]=++tot]=x; 31 for ( int i=1;i<=n;i++ ) cnt[map[a[i]]]++; 32 for ( int i=1;i<=tot;i++ ) cnt[i]+=cnt[i-1]; 33 for ( int i=1;i<=tot;i++ ) sum[i]=(sum[i-1]+1LL*(val[i+1]-val[i])%mod*cnt[i]%mod*cnt[i]%mod)%mod; 34 for ( int l,r,x;Q--; ) scanf("%d%d%d",&l,&r,&x),printf("%d ",(query(r,x)-query(l-1,x)+mod)%mod); 35 return 0; 36 }
B. 点分治
【题意】
对于一棵 $n$ 个点的树，求其点分治方案数。
两种点分治方案不同，当且仅当某个连通块的分治中心不同。
为了避免出现歧义，我们提供了一份暴力代码来具体描述这个算法。
1 const int mod=1e9+7; 2 const int maxn=5005; 3 bool vis[maxn]; 4 vector<int> e[maxn]; 5 int n; 6 inline void view_all(vector<int> &cur,int x,int fa){ 7 cur.push_back(x); 8 for(int p: e[x]){ 9 if (vis[p]) continue; 10 if (p == fa) continue; 11 view_all(cur, p, x); 12 } 13 } 14 inline int calc(int x){ 15 vector<int> cur; 16 int ans = 0; 17 view_all(cur, x, -1); 18 for(int w: cur){ 19 int res = 1; 20 vis[w] = 1; 21 for(int p: e[w]){ 22 if (vis[p]) continue; 23 res = 1ll * res * calc(p) % mod; 24 } 25 vis[w] = 0; 26 ans = (ans + res) % mod; 27 } 28 return ans; 29 } 30 inline int get_ans(){ 31 return calc(1); 32 }
【数据范围】$nle 5000$。
【题解】
考虑树形 $dp$。设 $f[i][j]$ 表示对 $i$ 的子树进行点分治，并且 $i$ 在点分树中的深度为 $j$ 的方案数。
把 $x$ 的儿子 $y$ 的DP数组合并上来时有：
$$f'[x][i]=sum_{j=1}^isum_{k=i-j}^n f[x][j] imes f[y][k] imes C_{i-1}^{j-1}$$
预处理 $f[y]$ 的后缀和，直接转移即可。
效率 $O(n^2)$。期望得分：100。
1 #include <bits/stdc++.h> 2 const int mod=1000000007; 3 int n,f[5010][5010],siz[5010],g[5010],h[5010],C[5010][5010]; 4 std::vector<int> e[5010]; 5 inline void dfs ( int u,int fr ) 6 { 7 f[u][1]=siz[u]=1; 8 for ( int v:e[u] ) if ( v!=fr ) 9 { 10 dfs(v,u); 11 for ( int y=n;~y;y-- ) h[y]=(h[y+1]+f[v][y])%mod; 12 for ( int x=1;x<=siz[u]+siz[v];x++ ) g[x]=0; 13 for ( int x=1;x<=siz[u];x++ ) for ( int y=0;y<=siz[v];y++ ) g[x+y]=(g[x+y]+1LL*f[u][x]*h[y]%mod*C[x+y-1][x-1])%mod; 14 siz[u]+=siz[v]; 15 for ( int x=1;x<=siz[u];x++ ) f[u][x]=g[x]; 16 } 17 } 18 signed main() 19 { 20 scanf("%d",&n); 21 for ( int i=1,u,v;i<n;i++ ) scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u); 22 for ( int i=0;i<=n;i++ ) 23 { 24 C[i][0]=1; 25 for ( int j=1;j<=i;j++ ) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 26 } 27 dfs(1,0);int Ans=0; 28 for ( int i=1;i<=n;i++ ) Ans=(Ans+f[1][i])%mod; 29 return !printf("%d ",Ans); 30 }