qaq题目好难啊
不过也还是可以水分的
今天做的THUWC模拟,简要放个题解:
【A:群】
题意
求对于大小为
分析
最近怎么总是遇到群论的题目……之前loj上碰到两道,今天又来……
这里
考虑一种比较特殊的情况,就是这个所构成的群是一个循环群,大概就是一个
很明显由于群的封闭性,考虑其中某一个
当然我们还需要的是进一步产生的这些置换不相同,那么就构成了一个循环群,循环群的阶显然就是循环节的长度
考虑如果
但是如果
然后还有一种情况,就是对于某个
然后考虑相当于依次地考虑
先枚举一波
下面引用原题解:
这 a 个大小为 2 的轮换在 j 和 k 中有两种组合方式.
第一种是两两组合, 比如说 i 中的两个轮换 (a b)(c d) 在 j 和 k 中分别对应 (a d)(b c) 和
(a c)(b d), 这样的话, 它对答案的贡献就是 2.
第二种是单个组合, 比如说 i 中的 (a b) 在 j 和 k 中分别对应 (a b) 和 (a)(b), 这样的贡献
仍然是 2.
因此这一部分的每一种方案的贡献是 2, 而所有方案的总贡献就求个和就可以了.
剩下的 n − 2a 个大小为 1 的轮换也有两种情况.
第一种是单个组合, 比如说 i 中的 (a) 在 j 和 k 中都是 (a), 这样的贡献是 1.
第二种是两两组合, 比如说 i 中的 (a)(b) 在 j 和 k 都是 (a b), 这样的贡献也是 1.
因此这一部分的贡献是所有轮换都不大于 2 的置换个数.
最后再乘一个排列数, 枚举哪些位置是大小为 1 的轮换就可以了.
【B:几何题】
题意
求
其中
分析
考虑利用数论函数变形的时候的常用套路,枚举这里三个维度上坐标的差,那么我们现在要求的实际上就是统计相应的坐标差的时候的方案数
先考虑一维的差的时候可以怎么做来推广下,我们可以考虑让
我们如法炮制搞一个
然后来一个三维FFT就解决了我们可以考虑利用类似进制转换的思路,考虑把
但是如果有负数怎么办?FFT怎么搞负指数?多项式求逆
直接加上个
然后这时再卡卡常就写过了(据说6s变2s?),两次FFT的做法不会……
【C:树】
题意
给定一棵无根树,每个点上有个权值,问将树全部剖分成路径,使得路径上的点权和为正数的方案数
分析
好久没写过超过110行的代码了……然后已经3.5K了……不过好像还是挺短的
先考虑这题有什么奇怪的暴力做法,我们考虑对于一个点
然后怎么优化呢?利用dsu on trees技术,就是启发式合并,先重链剖分,然后节点按照大小排个序就可以了
代码
# include <algorithm>
# include <cstring>
# include <utility>
# include <cstdio>
# define inf 1000000000
# define mod 1000000007
# define N 100005
# define ms(x) (x>=mod?x-mod:x)
# define mkp(x,y) make_pair(x,y)
# define fi first
# define se second
# define mem(x,v) memset(x,v,sizeof(v))
using namespace std;
typedef long long LL;
struct edge{ int to,nxt; } e[N+N]; int cnt;
int last[N];
struct node{ int tag,l,r,s; } t[N*40]; int sz;
int n;
int pre[N],suf[N];
int val[N];
int tim,l[N],r[N];
int siz[N],son[N],rt;
int f[N];
pair<int,int> a[N]; int as;
inline int read(){
int x=0,f=1; char c;
for (c=getchar();c < '0' || c >'9';c=getchar()) if (c == '-') f=-1;
for ( ;c>='0' && c<='9';c=getchar()) x=x*10+c-'0';
return x*f;
}
inline void addedge(int u,int v){
e[++cnt].to=v; e[cnt].nxt=last[u]; last[u]=cnt;
e[++cnt].to=u; e[cnt].nxt=last[v]; last[v]=cnt;
}
inline bool cmp(int x,int y){ return siz[x]>siz[y]; }
void dfs(int x,int fa){
val[x]+=val[fa]; siz[x]=1;
for (int i=last[x];i;i=e[i].nxt){
if (e[i].to == fa) continue;
dfs(e[i].to,x);
siz[x]+=siz[e[i].to];
}
l[x]=r[x]=tim+1;
for (int i=last[x];i;i=e[i].nxt)
if (e[i].to!=fa) son[++r[x]]=e[i].to;
++r[x]; tim=r[x]; sort(son+l[x]+1,son+r[x],cmp); //dsu on trees
}
inline int newnode(){
sz++; t[sz].tag=1;
t[sz].l=t[sz].r=t[sz].s=0;
return sz;
}
inline void pushdown(int d){
if (t[d].tag == 1) return;
int w=t[d].tag,x;t[d].tag=1;
x=t[d].l; if (x) t[x].tag=(LL)t[x].tag*w%mod,t[x].s=(LL)t[x].s*w%mod;
x=t[d].r; if (x) t[x].tag=(LL)t[x].tag*w%mod,t[x].s=(LL)t[x].s*w%mod;
}
void ins(int& d,int l,int r,int x,int y){
if (!d) d=newnode();
if (l<r) pushdown(d);
t[d].s=ms(t[d].s+y);
if (l == r) return;
int mid=((LL)l+(LL)r)>>1;
if (x <= mid) ins(t[d].l,l,mid,x,y);
else ins(t[d].r,mid+1,r,x,y);
}
int query(int d,int l,int r,int x,int y){
if (!d) return 0;
if (l<r) pushdown(d);
if (l==x && r==y) return t[d].s;
int mid=((LL)l+(LL)r) >> 1,ans;
if (y <= mid) ans+=query(t[d].l,l,mid,x,y);
if (x > mid) ans+=query(t[d].r,mid+1,r,x,y);
return ms(ans);
}
inline void get(int x,int fa,int s){
a[++as]=mkp(val[x],(LL)s*pre[r[x]-1]%mod);
for (int i=l[x]+1;i<r[x];++i) get(son[i],x,(LL)s*pre[i-1]%mod*suf[i+1]%mod);
}
void dp(int x,int fa){
for (int i=l[x]+2;i<r[x];i++) dp(son[i],x),sz=0,rt=newnode();
if (l[x]+1<r[x]) dp(son[l[x]+1],x);
pre[l[x]]=suf[r[x]]=1;
for (int i=l[x]+1;i<r[x];++i) pre[i]=(LL)pre[i-1]*f[son[i]]%mod;
for (int i=r[x]-1;i>l[x];--i) suf[i]=(LL)suf[i+1]*f[son[i]]%mod;
if (val[x]-val[fa]>=0) f[x]=ms(f[x]+pre[r[x]-1]);
f[x]=ms(f[x]+((LL)suf[l[x]+2]*query(rt,0,inf+inf,val[fa]+inf,inf+inf))%mod);
for (int i=l[x]+2;i<r[x];++i){
as=0; get(son[i],x,1);
for (int j=1;j<=as;++j){
if (a[j].fi-val[fa]>=0) f[x]=ms(f[x]+((LL)a[j].se*pre[i-1]%mod*suf[i+1]%mod)%mod);
f[x]=ms(f[x]+(LL)a[j].se*suf[i+1]%mod*query(rt,0,inf+inf,val[x]+val[fa]-a[j].fi+inf,inf+inf)%mod);
}
t[rt].tag=(LL)t[rt].tag*f[son[i]]%mod; t[rt].s=(LL)t[rt].s*f[son[i]]%mod;
for (int j=1;j<=as;++j) ins(rt,0,inf+inf,a[j].fi+inf,(LL)a[j].se*pre[i-1]%mod);
}
ins(rt,0,inf+inf,val[x]+inf,pre[r[x]-1]);
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
for (int i=1;i<=n;++i) val[i]=read();
for (int i=1; i<n;++i){
int x=read(),y=read();
addedge(x,y);
}
dfs(1,0);
sz=0; rt=newnode();
dp(1,0);
printf("%d\n",f[1]);
return 0;
}