西克
Description
Solution
跟 2021年省选A卷D2T1 一模一样，懒得讲了
不过这个题似乎有点卡空间，所以卡不过去
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 2000005
template <typename T> void read (T &x){char c = getchar ();x = 0;int f = 1;while (c < '0' || c > '9') f = (c == '-' ? -1 : 1),c = getchar ();while (c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar ();x *= f;}
template <typename T,typename ... Args> void read (T &x,Args& ... args){read (x),read (args...);}
template <typename T> void write (T x){if (x < 0) x = -x,putchar ('-');if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> void chkmax (T &a,T b){a = max (a,b);}
template <typename T> void chkmin (T &a,T b){a = min (a,b);}
unsigned int s1,s2;
vector <int> g[MAXN];
int n,q,a[MAXN],b[MAXN];
unsigned int rnd(){
s1*=s2,s2>>=s1&13,s2-=s1,s1^=s2;
return ((s1-s2)&(s1+s2))^(s1*s2>>4);
}
int ind,tur[MAXN],siz[MAXN],son[MAXN],dfn[MAXN],par[MAXN],dep[MAXN],Top[MAXN];
void dfs (int u,int fa){
siz[u] = 1,dep[u] = dep[fa] + 1,par[u] = fa;
for (Int v : g[u]){
dfs (v,u),siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs1 (int u,int top){
Top[u] = top,dfn[u] = ++ ind,tur[ind] = u;
if (son[u]) dfs1 (son[u],top);
for (Int v : g[u]) if (v != son[u]) dfs1 (v,v);
}
#define pii pair<int,int>
vector <pii> S1,S2;
vector <int> E[MAXN];
int nxt[MAXN][22],lst[MAXN][22];
int makeit (int u,int v){
int now = a[u];
S1.clear (),S2.clear ();
while (Top[u] ^ Top[v]){
if (dep[Top[u]] > dep[Top[v]]) S1.push_back ({dfn[Top[u]],dfn[u]}),u = par[Top[u]];
else S2.push_back ({dfn[Top[v]],dfn[v]}),v = par[Top[v]];
}
if (dep[u] <= dep[v]) S2.push_back ({dfn[u],dfn[v]});
else S1.push_back ({dfn[v],dfn[u]});
reverse (S2.begin(),S2.end());
for (pii it : S1) if (E[now].size()){
int L = it.first,R = it.second,whe = upper_bound (E[now].begin(),E[now].end(),R) - E[now].begin();
if (E[now][0] > R || E[now][-- whe] < L) continue;whe = E[now][whe];
for (Int i = 21;~i;-- i) if (lst[whe][i] >= L) whe = lst[whe][i];
now = b[tur[whe]];
}
for (pii it : S2) if (E[now].size()){
int L = it.first,R = it.second,whe = lower_bound (E[now].begin(),E[now].end(),L) - E[now].begin();
if (E[now][E[now].size() - 1] < L || E[now][whe] > R) continue;whe = E[now][whe];
for (Int i = 21;~i;-- i) if (nxt[whe][i] && nxt[whe][i] <= R) whe = nxt[whe][i];
now = b[tur[whe]];
}
return now;
}
signed main(){
freopen ("shik.in","r",stdin);
freopen ("shik.out","w",stdout);
read (n,q),read (s1,s2);
for (Int i = 1;i <= min (n,500000);++ i) read (a[i],b[i]);
for(int i=500001;i<=n;i++){
a[i]=rnd()%n+1;b[i]=a[rnd()%500000+1];
if(a[i]==b[i]){
++a[i];
if(a[i]>n)a[i]=1;
}
}
for (Int i = 2,x;i <= n;++ i) read (x),g[x].push_back (i);
dfs (1,0),dfs1 (1,1);
for (Int i = 1;i <= n;++ i){
int v = a[tur[i]];
E[v].push_back (i);
}
for (Int i = 1;i <= n;++ i){
int v1 = a[tur[i]],v2 = b[tur[i]],pos = lower_bound (E[v2].begin(),E[v2].end(),i) - E[v2].begin();
if (!pos) continue;
else{
lst[i][0] = E[v2][-- pos];
for (Int j = 1;(1 << j) <= i;++ j) lst[i][j] = lst[lst[i][j - 1]][j - 1];
}
}
for (Int i = n;i >= 1;-- i){
int v1 = a[tur[i]],v2 = b[tur[i]],pos = upper_bound (E[v2].begin(),E[v2].end(),i) - E[v2].begin();
if (pos == E[v2].size()) continue;
else{
nxt[i][0] = E[v2][pos];
for (Int j = 1;(1 << j) <= n - i + 1;++ j) nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
}
int ans = 0;
while (q --> 0){
int x,y;read (x,y);
ans ^= makeit (x,y);
}
write (ans),putchar ('\n');
return 0;
}
尼特
Description
Solution
还没做出来，之后再补坑吧
苯为
Description
Solution
首先不难看出一个长度为 \(n\) 的环会产生的贡献是：
\[(k-1)^{n(A+1)}+(-1)^{n(A+1)}\times (k-1) \]那么，答案就是：
\[\sum_{s}\sum_{t} ((k-1)^{d(A+1)+(-1)^{d(A+1)}(k-1)})\times (k-1)^{(n-d)(A+1)} \] \[=n^2\times (k-1)^{n(A+1)}+(k-1)\sum_{s}\sum_{t} (-1)^{d(A+1)}(k-1)^{(n-d)(A+1)} \]然后你发现后来那个可以视作：环上的点贡献为 \((-1)^{A+1}\)，不在环上的点贡献为 \((k-1)^{A+1}\)，树的贡献之积的和。
这个可以直接 dp，设 \(f_u\) 表示还没有将两条不转向的链合并时链头为 \(u\) 的贡献之和，转移显然。
复杂度 \(\Theta(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define int long long
#define mod 421969921
#define MAXN 1000005
template <typename T> void read (T &x){char c = getchar ();x = 0;int f = 1;while (c < '0' || c > '9') f = (c == '-' ? -1 : 1),c = getchar ();while (c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar ();x *= f;}
template <typename T,typename ... Args> void read (T &x,Args& ... args){read (x),read (args...);}
template <typename T> void write (T x){if (x < 0) x = -x,putchar ('-');if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> void chkmax (T &a,T b){a = max (a,b);}
template <typename T> void chkmin (T &a,T b){a = min (a,b);}
int n,A,K,siz[MAXN];
vector <int> g[MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){
a %= mod,b %= (mod - 1);
int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);
return res;
}
int upd (int x){return x < 0 ? x + mod : x;}
int inv (int x){return qkpow (x,mod - 2);}
void Add (int &a,int b){a = add (a,b);}
void Sub (int &a,int b){a = dec (a,b);}
int v1,v2,ans,f[MAXN],pw1[MAXN],pw2[MAXN];//v1表示在链上的贡献，v2表示不在链上的贡献
void dfs (int u,int fa){
siz[u] = 1;int res = 0;
for (Int v : g[u]) if (v ^ fa){
dfs (v,u);
res = add (mul (res,pw2[siz[v]]),mul (f[u],f[v]));
f[u] = add (mul (f[u],pw2[siz[v]]),mul (f[v],mul (pw2[siz[u] - 1],v1)));
siz[u] += siz[v];
}
Add (ans,mul (v1,pw2[n - 1])),Add (ans,mul (2,mul (res,pw2[n - siz[u]]))),Add (ans,mul (2,mul (f[u],pw2[n - siz[u]]))),Add (f[u],mul (v1,pw2[siz[u] - 1]));
}
signed main(){
freopen ("ber.in","r",stdin);
freopen ("ber.out","w",stdout);
read (n,A,K),A = A % (mod - 1),K %= mod;
for (Int i = 2,x,y;i <= n;++ i) read (x,y),g[x].push_back (y),g[y].push_back (x);
v1 = A + 1 & 1 ? mod - 1 : 1,v2 = qkpow (K - 1,A + 1);
pw1[0] = pw2[0] = 1;for (Int i = 1;i <= n;++ i) pw1[i] = mul (pw1[i - 1],v1),pw2[i] = mul (pw2[i - 1],v2);
dfs (1,0),ans = add (mul (ans,K - 1),mul (mul (n,n),qkpow (K - 1,n * (A + 1) % (mod - 1))));
write (ans),putchar ('\n');
return 0;
}
神奇纸牌
Description
Solution
考试的时候脑抽了。
可以想到的是，可以将问题转换为：有 \(n\) 次操作，\(4\) 种颜色，每次操作可以将若干个颜色两两连边，问最后度数不为 \(0\) 的颜色都联通的方案数。
然后你可以设 \(f_{i,S}\) 表示考虑了前 \(i\) 个，联通及出现状态为 \(S\) 的方案数，然后你发现状态数为 \(52\)，就可以直接矩阵快速幂了。
复杂度 \(\Theta(52^3\times \log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define int long long
#define MAXN 85
template <typename T> void read (T &x){char c = getchar ();x = 0;int f = 1;while (c < '0' || c > '9') f = (c == '-' ? -1 : 1),c = getchar ();while (c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar ();x *= f;}
template <typename T,typename ... Args> void read (T &x,Args& ... args){read (x),read (args...);}
template <typename T> void write (T x){if (x < 0) x = -x,putchar ('-');if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> void chkmax (T &a,T b){a = max (a,b);}
template <typename T> void chkmin (T &a,T b){a = min (a,b);}
int n,mod;
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){
int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);
return res;
}
int inv (int x){return qkpow (x,mod - 2);}
void Add (int &a,int b){a = add (a,b);}
int tot;
map <vector <int>,int> mp;
map <int,vector <int> > tur;
vector <int> Snow;
void dfs (int now,int cnt){
if (now > 4){
if (mp.find (Snow) != mp.end()) ;
else mp[Snow] = ++ tot,tur[tot] = Snow;
return ;
}
for (Int i = 0;i <= cnt;++ i) Snow.push_back (i),dfs (now + 1,cnt),Snow.pop_back ();
Snow.push_back (cnt + 1),dfs (now + 1,cnt + 1),Snow.pop_back ();
}
int h[55][55] = {
{},
{0,1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 1 , 1 , 4 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 1 , 1 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 1 , 0 , 0 , 0 , 1 , 4 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 1 , 0 , 0 , 0 , 1 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 4 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 1 , 1 , 3 , 1 , 1 , 3 , 1 , 3 , 8 , 3 , 1 , 3 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 5 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 5 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 5 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 4 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 4 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 1 , 1 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 1 , 3 , 8 , 3 , 1 , 3 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 5 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 5 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 5 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 1 , 0 , 0 , 0 , 1 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 3 , 8 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 5 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 3 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 3 , 0 , 0 , 1 , 0 , 0 , 0 , 3 , 0 , 0 , 8 , 0 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0},
{0,1 , 1 , 1 , 3 , 1 , 1 , 3 , 1 , 3 , 7 , 3 , 1 , 3 , 3 , 1 , 1 , 3 , 1 , 3 , 7 , 3 , 1 , 3 , 3 , 1 , 3 , 7 , 3 , 7 , 16 , 7 , 3 , 7 , 9 , 3 , 1 , 3 , 3 , 1 , 3 , 7 , 9 , 3 , 3 , 9 , 7 , 3 , 1 , 3 , 3 , 3 , 1},
{0,0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 0 , 3 , 1 , 0 , 9 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 0 , 1},
{0,0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 5 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0},
{0,0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 3 , 9 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 3 , 0 , 1},
{0,0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 7 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0},
{0,0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 6 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1},
{0,0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 5 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 5 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 4 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 5 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 3 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 0 , 1 , 3 , 9 , 0 , 3 , 0 , 0 , 0 , 0 , 1 , 3 , 0 , 3 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 7 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 6 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 5 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 7 , 0 , 1 , 0 , 1 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 3 , 1 , 0 , 0 , 0 , 0 , 3 , 0 , 9 , 3 , 1 , 0 , 3 , 3 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 6 , 0 , 0 , 0 , 0 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 4 , 0 , 0 , 0 , 0},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 6 , 0 , 0 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 6 , 0 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 6 , 1},
{0,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 5},
};
struct Matrix{
int mat[55][55];
Matrix(){memset (mat,0,sizeof (mat));}
int * operator [] (const int key){return mat[key];}
Matrix operator * (const Matrix &p)const{
Matrix New;
for (Int i = 1;i <= 52;++ i)
for (Int j = 1;j <= 52;++ j)
for (Int k = 1;k <= 52;++ k)
Add (New[i][k],mul (mat[i][j],p.mat[j][k]));
return New;
}
}A;
Matrix qkpow (Matrix A,int b){
Matrix res;
for (Int i = 1;i <= 52;++ i) res[i][i] = 1;
while (b){
if (b & 1) res = res * A;
A = A * A,b >>= 1;
}
return res;
}
signed main(){
freopen ("uno.in","r",stdin);
freopen ("uno.out","w",stdout);
dfs (1,0);
read (n,mod);int tot = 52;
for (Int i = 1;i <= tot;++ i)
for (Int j = 1;j <= tot;++ j)
A[i][j] = h[i][j];
A = qkpow (A,n);
int ans = 0;
for (Int S = 0;S < (1 << 4);++ S){
vector <int> H;
for (Int i = 0;i < 4;++ i) H.push_back (S >> i & 1);
ans += A[mp[H]][1],ans %= mod;
}
write (ans),putchar ('\n');
return 0;
}
凌乱平衡树
Description
Solution
~~ 暴力都83分了还写什么正解啊？~~
不难想到的是，\(\sum dep=\sum siz\)，而我们的答案就是 \(\sum sizA_i+\sum sizB_i\) 再加上在合并是被合并的那一方的子树大小。
那么，我们就可以转换成，把左边的树的右儿子不断递归产生的链的 \(siz\) 序列当作 \(A_{1,2,...}\)，右边的树的左儿子不断递归