2017 ACM-ICPC 亚洲区（西安赛区）网络赛 A Tree

https://nanti.jisuanke.com/t/A1267
There is a tree with nn nodes, at which attach a binary 64*6464∗64 matrix M_i (1 \le i \le n)M
i
​
(1≤i≤n). There are qq queries for matrix multiplication on the path from node aa to node bb modulo 22. To avoid massive input dataset, M_i(1\le i \le n)M
i
​
(1≤i≤n) is attained by the following algorithm:

Input a random seedseed (unsigned long long)

思路：首先对于所有询问(u.v)，将每个点u需要计算路径的所有v记录下来，因为矩阵乘法不满足交换律，记得标记下是u到v还是v到u，然后点分治时对于一个重心root，可以分别处理它的每一颗子树，对于子树上的每一个节点，算出它到子树根节点的矩阵乘积（由子树根到该节点以及反方向的都需要算出来），并且看该节点u是否有一个对应节点v需要询问答案，并且节点v出现在其他子树中，出现的话将答案计算出来即可
因为点分治有logn层，每层访问所有节点需要询问的答案，也就n+q的复杂度，然后因为是64位的01矩阵，压位后矩阵乘复杂度为64*64，最终复杂度为$O(64\ast 64\ast logn\ast (n+q)$
(初始化有些细节没注意调一万年。。。）

#include
#define MAXN 3010
#define MAXM 30010
#define MOD 19260817
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
using namespace std;
int head[MAXN],tot;
struct edge
{int v,nxt;
}edg[MAXN << 1];
inline void addedg(int u,int v)
{edg[tot].v = v;edg[tot].nxt = head[u];head[u] = tot++;
}
struct matrix
{ull a[64];
}mat[MAXN],pre[MAXN],sub[MAXN],mm;
inline matrix mul(matrix n1,matrix n2)
{matrix ans;for(int i = 0;i < 64;++i){ans.a[i] = 0;for(int j = 0;j < 64;++j)if(n1.a[i] & (1ull <<(63-j)))ans.a[i] ^= n2.a[j];}return ans;
}
int mx,Size,root,sz[MAXN];
bool vis[MAXN];
inline void getroot(int u,int f)
{int mson = 0,v;sz[u] = 1;for(int i = head[u];i != -1;i = edg[i].nxt){v = edg[i].v;if(vis[v] || v == f) continue;getroot(v,u);sz[u] += sz[v];mson = max(mson,sz[v]);}mson = max(mson,Size-sz[u]);if(mson < mx) mx = mson,root = u;
}
ll pw19[65],pw26[65];
inline ll cal(matrix ma)
{ll ans = 0;for(int i = 0;i < 64;++i)for(int j = 0;j < 64;++j)if(ma.a[i] & (1ull << (63-j)))ans = (ans + pw19[i+1]* pw26[j+1] % MOD)%MOD;return ans;
}
int n,q;
ll ans[MAXM];
struct node
{int v,tp,id;
};
vector ve[MAXN];
ull seed;
bool vv[MAXN];
int vvid[MAXN],cc,cnt,id[MAXN];
matrix dispre[MAXN],dissub[MAXN];
inline void getdis(int u,int f,matrix pr,matrix sb)
{int v;pr = mul(pr,mat[u]);sb = mul(mat[u],sb);dispre[u] = pr,dissub[u] = sb,id[++cnt] = u;for(int i = 0;i < ve[u].size();++i){if(vv[ve[u][i].v]){if(ve[u][i].tp == 1)ans[ve[u][i].id] = cal(mul(sb,pre[ve[u][i].v]));elseans[ve[u][i].id] = cal(mul(sub[ve[u][i].v],pr));}}for(int i = head[u];i != -1;i = edg[i].nxt){v = edg[i].v;if(v == f || vis[v]) continue;getdis(v,u,pr,sb);}
}
inline void solve(int u,int ssize)
{vis[u] = 1;cc = 0;vv[u] = 1;vvid[++cc] = u,pre[u] = sub[u] = mat[u];for(int i = 0;i < ve[u].size();++i){if(ve[u][i].v == u)ans[ve[u][i].id] = cal(mat[u]);}int v;for(int i = head[u];i != -1;i = edg[i].nxt){v = edg[i].v;if(vis[v]) continue;cnt = 0;getdis(v,v,mm,mm);for(int j = 1;j <= cnt;++j){pre[id[j]] = mul(mat[u],dispre[id[j]]),sub[id[j]] = mul(dissub[id[j]],mat[u]);vv[id[j]] = 1,vvid[++cc] = id[j];}}for(int i = 1;i <= cc;++i)vv[vvid[i]] = 0;for(int i = head[u];i != -1;i = edg[i].nxt){v = edg[i].v;if(vis[v]) continue;Size = sz[v] < sz[u] ? sz[v] : ssize - sz[u];mx = INF;getroot(v,v);solve(root,Size);}
}
inline void init()
{memset(head,-1,sizeof(int)*(n+1));memset(vis,false,sizeof(bool)*(n+1));for(int i = 1;i <= n;++i)ve[i].clear();tot = 0;Size = n,mx = INF;
}
int main()
{pw19[0] = pw26[0] = 1;for(int i = 1;i <= 64;++i){pw19[i] = pw19[i-1]  * 19 % MOD;pw26[i] = pw26[i-1] * 26 % MOD;}for(int i = 0;i < 64;++i)mm.a[i] = (1ull << (63-i));while(~scanf("%d%d",&n,&q)){init();int u,v;for(int i = 1;i < n;++i){scanf("%d%d",&u,&v);addedg(u,v);addedg(v,u);}scanf("%llu",&seed);for(int i = 1; i <= n; ++i) {memset(mat[i].a,0,sizeof(mat[i].a));for(int p = 0; p < 64; ++p) {seed ^= seed * seed + 15;for(int q = 0; q < 64; ++q) {mat[i].a[p] |= ((((seed >> q) & 1)*1ull) << (63-q));}}}for(int i = 1;i <= q;++i){scanf("%d%d",&u,&v);ve[u].push_back(node{v,1,i});if(u != v)ve[v].push_back(node{u,2,i});}getroot(1,1);solve(root,Size);for(int i = 1;i <= q;++i)printf("%lld\n",ans[i]);}return 0;
}
/*6 6
4 1
3 4
6 4
5 3
2 3
19260817
4 4
1 1
2 2
3 3
5 5
6 6*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！