洛谷P6569 魔法值

2022-09-23 02:12:09 字數 1412 閱讀 7873

h 國的交通由 \(n\) 座城市與 \(m\) 條道路構成,城市與道路都從 \(1\) 開始編號,其中 \(1\) 號城市是 h 國的首都。h 國中一條道路將把兩個不同城市直接相連,且任意兩個城市間至多有一條道路。

h 國是一個信奉魔法的國家,在第 \(j\) 天,\(i\) 號城市的魔法值為 \(f_\)。h 國的魔法師已觀測到第 0 天時所有城市的魔法值 \(f_\),且他們還發現,之後的每一天每個城市的魔法值,都將會變為所有與該城市直接相連的城市的前一天魔法值的異或值,即

\[f_=f_\oplus f_\oplus \cdots\oplus f_

\]其中 \(j\ge 1\),\(v_1,v_2,\cdots,v_k\) 是所有與 \(x\) 號城市直接相連的城市,\(\oplus\) 為異或運算。

現在 h 國的國王問了你 \(q\) 個問題,對於第 \(i\)(\(1\le i\le q\))個問題你需要回答:第 \(a_i\) 天時首都的魔法值是多少。

顯然第 \(t\) 天城市 \(i\) 的魔法值 \(f_\) 為所有距離 \(i\) 長度為 \(t\) 且道路有奇數條的點 \(j\) 的第 0 天權值異或和。

那麼這個玩意可以用矩陣乘法求,對於每一個詢問跑一次矩陣乘法,時間複雜度 \(o(qn^3 \log t)\)。

但是我們發現每次初始矩陣都是一樣的,只是矩陣乘法的次數不同,而且題目中只要求點 1 的魔法值,所以我們可以預處理出初始矩陣自乘 \(2^k(0\leq k\leq 31)\) 次的矩陣 \(a[k]\),然後對於每一個詢問 \(t\),第 \(t\) 天對點 1 有貢獻的點就是 \(t\) 二進位制下為 1 的位置的矩陣相乘後,矩陣中為 1 的點集。

考慮到只要求點 1 的魔法值,所以最終每個詢問的矩陣是一個 \(1\times n\) 的矩陣,此時單次矩陣乘法時間複雜度為 \(o(n^2\log t)\)。

這樣總時間複雜度為 \(o(n^3\log t+qn^2 \log t)\)。

#include #include #include using namespace std;

typedef long long ll;

const int n=110,lg=31;

int n,m,q;

ll f[n];

bool flag;

struct matrix

}a[lg+1],mat;

int main()

for (int l=1;l<=lg;l++)

a[l]=a[l-1]*a[l-1];

flag=1;

while (q--)

for (int i=1;i<=n;i++)

ans^=(1ll*f[i]*mat.a[1][i]);

printf("%lld\n",ans);

} return 0;

}

洛谷P1822 魔法指紋

對於任意一個至少兩位的正整數n,按如下方式定義magic n 將n按十進位制順序寫下來,依次對相鄰兩個數寫下差的絕對值。這樣,得到了一個新數...

洛谷P2801 教主的魔法

一道分塊的好題。 這題分塊後,對於兩種操作 分塊後,我們將每一塊中的數排序,這樣每一塊中的查詢可以通過二分完成。 對於區間的修改,如果覆蓋了...

洛谷P1822 魔法指紋

這道題事實上解並不多,所以我們倒過來從 7 開始搜尋。主過程中為廣搜,而函式深搜進行拓展。其實是對於前導 0 刪去的情況也要考慮,否則只有...