A. 异或
考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。
考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXM = 60;
LL f[MAXM+1],pw[MAXM+1];
int main(){
pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1;
LL n;scanf("%lld",&n);
FOR(i,1,MAXM){
FOR(j,0,i){// 结尾有多少个 1
f[i] += 1ll*(j+1)*pw[std::max(0,i-j-1)];
}
}
LL ans = 0;
ROF(i,MAXM,0){
if(!((n>>i)&1)) continue;
ans += f[i];
}
if(n&1) ans++;
printf("%lld\n",ans);
return 0;
}
// [0,n-1] 偶数贡献 1 奇数贡献末尾连续 1 数量+1B.
先考虑 $n=2$ 怎么做：我们设 $f_{a,b}$ 表示剩 $a$ 个颜色 $1$，$b$ 个颜色 $2$ 的答案是什么。
我们设放在颜色 $1$ 上的钱为 $x$，颜色 $2$ 上的必然为 $1-x$，所以能得到的钱是 $\min(2xf_{a-1,b},2(1-x)f_{a,b-1})$。
能解出来 $x=\frac{f_{a,b-1}}{f_{a-1,b}+f_{a,b-1}}$，也就是有方程 $f_{a,b} = \frac{2f_{a-1,b}f_{a,b-1}}{f_{a-1,b}+f_{a,b-1}}$。
那么我们设 $g_{a,b} = f_{a,b}2^{a+b}$，有转移方程 $g_{a,b} = \frac{g_{a-1,b}g_{a,b-1}}{g_{a-1,b}+g_{a,b-1}}$，考虑两边取倒数，也就是
$$ \frac{1}{g_{a,b}} = \frac{g_{a-1,b}+g_{a,b-1}}{g_{a-1,b}g_{a,b-1}} = \frac{1}{g_{a-1,b}}+\frac{1}{g_{a,b-1}} $$
我们发现 $\frac{1}{g_{a,b}}$ 实际上是从 $(0,0)$ 走到 $(a,b)$ 的方案数，也就是 $\binom {a+b}{a}$。
这样就能通过 $n=2$ 的部分。
$n>2$ 的部分：我们考虑写出类似的状态：也就是有 $n$ 维。这个倒数也等价于从 $(0,0,\ldots,0)$ 走到 $(a_1,a_2,\ldots,a_n)$ 的方案数，也就是 $\binom{\sum_i a_i}{a_1,a_2,\ldots,a_n}$，所以答案就是 $\frac{n^{\sum_i a_i}}{\binom{\sum_i a_i}{a_1,a_2,\ldots,a_n}}$。
比赛的时候解出了不等式就是按照比值取，相当于先手策略确定了，所以直接按照后手整个小根堆贪心。。然而式子是一样的。。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e6 + 5;
const int ha = 998244353;
int n,a[MAXN];
inline int qpow(int a,int n=ha-2){
int res = 1;
while(n){
if(n & 1) res = 1ll*res*a%ha;
a = 1ll*a*a%ha;
n >>= 1;
}
return res;
}
/*
//int f[1005][1005];
double f[1005][1005],g[1005][1005];
int mx = 0;
namespace BF{
inline void Solve(){
f[0][0] = 1;
FOR(i,1,10) f[i][0] = f[0][i] = 2*f[i-1][0];
FOR(i,1,10){
FOR(j,1,10){
f[i][j] = 2.0*f[i][j-1]*f[i-1][j]/(f[i-1][j]+f[i][j-1]);
g[i][j] = 1.0*f[i][j-1]/(f[i-1][j]+f[i][j-1]);
// f[i][j] = 2ll*f[i][j-1]%ha*f[i-1][j]%ha*qpow((f[i-1][j]+f[i][j-1])%ha)%ha;
}
}
FOR(i,1,10){
FOR(j,1,10){
printf("%.5f=%.5f%c",f[i][j],1.0*i/(i+j)," \n"[j==10]);
}
}
}
}
*/
int main(){
std::priority_queue<int,std::vector<int>,std::greater<int> > q;
int sm = 0;
scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),q.push(a[i]),sm += a[i];
int ans = 1;
while(!q.empty()){
int v = q.top();q.pop();
ans = 1ll*ans*n%ha*qpow(sm)%ha*v%ha;
--v;if(v) q.push(v);--sm;
}
printf("%d\n",ans);
return 0;
}
// 策略: 按照比例分配C
套路题。
我们有：
$$ x^{k} = \sum_{i = 0}^k \left[^k_i\right] x^{\underline i} $$
相当于对于每个 $i$，计算每一条路径的贡献的和，一条长度为 $len$ 的路径的贡献是 $\binom{len} i i!$，也就是有序选出 $i$ 个不同的边。
于是可以搞个 dp 了：设 $f_{v,i}$ 表示 $v$ 点，端点一个点是 $v$ ，另一个点在子树内的所有的长度为 $i$ 的链的选取方案，转移直接从儿子合并上来就行。我们在转移的过程中会得到 $g_{x,i}$ 表示加了到父亲 $v$ 的边后的选取方案，那么所以 $lca = v$ 的链是至多用两个儿子的 $g$ 拼起来的，写个树形背包就行了。根据树形背包的复杂度来说，复杂度是 $O(nk)$。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e6 + 5;
const int MAXM = 100 + 5;
const int ha = 998244353;
inline char nc(){
#define SIZE 1000000+3
static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
if(p1 == p2){
p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
if(p1 == p2) return -1;
}
return *p1++;
#undef SIZE
}
template <typename T>
inline void read(T &x){
x = 0;int flag = 0;char ch = nc();
while(!isdigit(ch)){
if(ch == '-') flag = 1;
ch = nc();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + (ch^'0');
ch = nc();
}
if(flag) x = -x;
}
inline void add(int &x,int y){
x += y-ha;x += x>>31&ha;
}
int S2[MAXM][MAXM],C[MAXM][MAXM];
inline void prework(){
S2[0][0] = 1;C[0][0] = 1;
FOR(i,1,MAXM-1){
C[i][0] = 1;
FOR(j,1,i){
S2[i][j] = (S2[i-1][j-1]+1ll*S2[i-1][j]*j%ha)%ha;
C[i][j] = (C[i-1][j]+C[i-1][j-1])%ha;
}
}
}
int n,k;
std::vector<int> G[MAXN];
int f[MAXN][MAXM],tmp[MAXM];
int h[MAXM];
int sz[MAXN];
inline void dfs(int v,int fa=0){
f[v][0] = 1;sz[v] = 1;
for(auto x:G[v]){
if(x == fa) continue;
dfs(x,v);
}
for(auto x:G[v]){
if(x == fa) continue;
FOR(i,0,k){
tmp[i] = f[x][i];
if(i) add(tmp[i],1ll*f[x][i-1]*i%ha);
}
// 任选两个合并
FOR(a,0,std::min(k,sz[v])){
FOR(b,0,std::min(k,sz[x])){
if(a+b > k) break;
add(h[a+b],1ll*f[v][a]*tmp[b]%ha*C[a+b][b]%ha);
}
}
FOR(i,0,k) add(f[v][i],tmp[i]);
sz[v] += sz[x];
}
}
int main(){
// freopen("C.in","r",stdin);
prework();
read(n);read(k);
FOR(i,2,n){
int u,v;read(u);read(v);
G[u].pb(v);G[v].pb(u);
}
dfs(1);
int ans = 0;
FOR(i,0,k){
int gx = 1ll*h[i]*S2[k][i]%ha;
add(ans,gx);
}
printf("%d\n",ans);
return 0;
}D
注意：本题空间限制 256 M。
这个树上的问题肯定是强于链上的问题的，所以我们要考虑根号分治。
对于 $x \leq \sqrt n$ 的部分：我们可以枚举每一个 $x$ ，分别计算操作对所有询问的贡献，如果确定了 $u$ 是 $v$ 的祖先，并且有操作 $(u,x,y,z)$，那么这个操作对询问 $v$ 有影响当且仅当 $dep_v \equiv dep_u+y \pmod x$，所以我们再按照 $\bmod x$ 的值分组，每组内相当于就只有子树限制了。需要支持区间加和单点查询，如果直接做复杂度会变成 $O(n\sqrt n \log n)$，但是我们发现我们的修改有 $O(q)$ 次，询问有 $O(q \sqrt n)$ 次（对于每个 $x$ 都要把所有询问放进去），所以可以用一个 $O(\sqrt n)$ 修改，$O(1)$ 查询的东西将复杂度平衡到 $O(q\sqrt n)$。
对于 $x > \sqrt n$ 的部分：相当于我们可以暴力将每个操作 apply 到所有可能的深度上，并且将询问挂在对应的深度上，对于每个深度，我们现在只有了子树限制，相当于要支持区间加，单点查。我们发现修改的次数有 $O(q\sqrt n)$ 次（每个操作会贡献到 $O(\sqrt n)$ 个深度上），查询的次数只有 $O(q)$ 次，所以我们将询问差分一下，变成了 $O(q\sqrt n)$ 次单点修改，$O(q)$ 次前缀查询，也可以用分块根号平衡到 $O(q \sqrt n)$。
但是我们发现我们如果对于每个深度都存下来有关于它的所有修改操作显然就爆炸了。。空间复杂度是 $O(q \sqrt n)$ 的，但是我们注意到每个操作贡献到的两个深度的差至少是 $\sqrt n$ ，所以我们可以每 $\sqrt n$ 个深度一起处理，每次只存这些深度的询问和修改，这样总复杂度还是 $O(q\sqrt n)$ 的，并且空间复杂度降到了 $O(q+n)$。
注意有个细节：如果你的根号数据结构实现的 reset （清空）是存下所有操作并反向做的话，并且是在 modify 开头将操作加入 vector 的话，用 vector 记录的时候不要把删除操作加入 vector！！这样导致在遍历一个 vector 的时候加入新元素，会 UB。。。调了一下午。。主要是 Mac 测不出来这个错误，并且 OJ 上还能过大部分点。。
还要注意：vector 的 clear 不会释放空间，要用 std::vector<element>().swap。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 4e5 + 5;
inline char nc(){
#define SIZE 1000000+3
static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
if(p1 == p2){
p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
if(p1 == p2) return -1;
}
return *p1++;
#undef SIZE
}
template <typename T>
inline void read(T &x){
x = 0;int flag = 0;char ch = nc();
while(!isdigit(ch)){
if(ch == '-') flag = 1;
ch = nc();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + (ch^'0');
ch = nc();
}
if(flag) x = -x;
}
struct DS1{// 区间加O(sqrt) 单点查O(1)
int B,N;
int tag[MAXN],bel[MAXN],a[MAXN];
std::vector<std::pair<P,int> > S;
inline void init(int size){
N = size;B = std::sqrt(1.0*N);S.clear();
FOR(i,1,N) bel[i] = (i-1)/B+1,a[i] = 0;
FOR(i,1,bel[N]) tag[i] = 0;
}
inline void modify(int l,int r,int d,bool tg=1){
if(tg) S.pb(MP(MP(l,r),d));
if(bel[l] == bel[r]){
FOR(i,l,r) a[i] += d;
return;
}
FOR(i,l,bel[l]*B) a[i] += d;
FOR(i,bel[l]+1,bel[r]-1) tag[i] += d;
FOR(i,(bel[r]-1)*B+1,r) a[i] += d;
}
inline int query(int x){
return tag[bel[x]]+a[x];
}
inline void reset(){
for(auto x:S) modify(x.fi.fi,x.fi.se,-x.se,0);
//std::vector<std::pair<P,int> >().swap(S);
S.clear();
}
}ds1;
struct DS2{
int B,N;
int a[MAXN],sm[MAXN],bel[MAXN];
std::vector<std::pair<P,int> > S;
inline void init(int size){
N = size;B = std::sqrt(1.0*N);S.clear();
FOR(i,1,N) bel[i] = (i-1)/B+1,a[i] = 0;
FOR(i,1,bel[N]) sm[i] = 0;
}
inline void modify(int l,int r,int d,int tg=1){
if(tg) S.pb(MP(MP(l,r),d));
a[l] += d;sm[bel[l]] += d;++r;
if(r <= N) a[r] -= d,sm[bel[r]] -= d;
}
inline int query(int x){
int res = 0;
FOR(i,1,bel[x]-1) res += sm[i];
FOR(i,(bel[x]-1)*B+1,x) res += a[i];
return res;
}
inline void reset(){
for(auto x:S) modify(x.fi.fi,x.fi.se,-x.se,0);
//std::vector<std::pair<P,int> >().swap(S);
S.clear();
}
}ds2;
int n,m;
std::vector<int> G[MAXN];
int dep[MAXN],dfn[MAXN],sz[MAXN];
inline void dfs(int v,int fa=0){
static int ts = 0;
dfn[v] = ++ts;dep[v] = dep[fa]+1;sz[v] = 1;
for(auto x:G[v]){
if(x == fa) continue;
dfs(x,v);sz[v] += sz[x];
}
}
struct Node{
int opt,v,x,y,z,id;
Node(int opt=0,int v=0,int x=0,int y=0,int z=0,int id=0) : opt(opt),v(v),x(x),y(y),z(z),id(id) {}
}q[MAXN];
int tot;
std::vector<Node> qq[MAXN];
int ans[MAXN];
int main(){
// freopen("D.in","r",stdin);
// freopen("D.out","w",stdout);
read(n);read(m);
FOR(i,2,n){
int u,v;read(u);read(v);
G[u].pb(v);G[v].pb(u);
}
dfs(1);
FOR(i,1,m){
read(q[i].opt);read(q[i].v);
if(q[i].opt == 1) read(q[i].x),read(q[i].y),read(q[i].z);
q[i].id = i;
}
int B = std::sqrt(1.0*n);
ds1.init(n);ds2.init(n);
FOR(x,1,B){
tot = 0;
FOR(i,1,m){
if(q[i].opt == 1){
if(q[i].x == x) qq[(q[i].y+dep[q[i].v])%x].pb(q[i]);
}
else{
qq[dep[q[i].v]%x].pb(q[i]);
}
}
FOR(y,0,x-1){
ds1.reset();
for(auto v:qq[y]){
if(v.opt == 1) ds1.modify(dfn[v.v],dfn[v.v]+sz[v.v]-1,v.z);
else ans[v.id] += ds1.query(dfn[v.v]);
}
}
FOR(i,0,x-1) qq[i].clear();
// FOR(i,0,x-1) std::vector<Node>().swap(qq[i]);//qq[i].clear();
}
// FOR(i,0,B) std::vector<Node>().swap(qq[i]);
// 卡空间 考虑每次只处理[l,l+B]深度的询问 这样每个操作最多进来一次
// 毒瘤出题人！！！
for(int l = 1,r;l <= n;l = r+1){
r = std::min(n,l+B);
FOR(i,1,m){
if(q[i].opt == 1){
if(q[i].x > B && r >= dep[q[i].v]+q[i].y){
int k = (r-q[i].y-dep[q[i].v])/q[i].x;
int d = k*q[i].x+q[i].y+dep[q[i].v];
while(l <= d) qq[d].pb(q[i]),d -= q[i].x;
}
}
else if(dep[q[i].v] >= l && dep[q[i].v] <= r) qq[dep[q[i].v]].pb(q[i]);
}
FOR(i,l,r){
ds2.reset();
for(auto x:qq[i]){
if(x.opt == 1) ds2.modify(dfn[x.v],dfn[x.v]+sz[x.v]-1,x.z);
else ans[x.id] += ds2.query(dfn[x.v]);
}
}
FOR(i,l,r) std::vector<Node>().swap(qq[i]);//qq[i].clear();
// 注意:vector clear 不会释放空间
}
FOR(i,1,m) if(q[i].opt == 2) printf("%d\n",ans[i]);
return 0;
}