同余最短路 新手入門
同余最短路 入門
關于同余最短路, 我這個蒟蒻剛剛遇到, 大概看了一下, 感覺挺有意思, 故寫了這篇博客.
(暫時未完工)
注意
因作者不喜歡太過于正式的表述, 故會使用一些不正規的語言, 介意者請注意.
僅有簡單例題, 已經熟練掌握此技巧者可以離開了, 我這個蒟蒻剛剛學會......
不多說了, 我們開始吧.
思想
想差分約束一樣, 當我們發現可以通過同余構造類似帶權有向邊的狀態時
我們就可以將一些問題轉化為最短路問題, 使用一些效率強大的算法解決問題
具體很難直接說, 我們通過例題看
例題:
題意の簡述
給定 \(x, y, z, h\), 對于 \(k\in[1,h]\), 詢問有多少個 \(k\) 可以滿足: \(ax+by+cz=k\) (OI wiki 的題意簡化)
數據范圍: \(0\le a,b,c\) , \(1\le x,y,z \le 10^5\) , \(h \le 2^{63}-1\)
看著像不像數學題, 我看著也像, 但是如果我們深入思考會發現難以求解
我們若想求解, 我們需要固定兩個變量 (反正我覺得需要)
However, 我們似乎沒有辦法用數學做到
我有一計
來自神秘先輩的記憶碎片告訴我們, 對于這個問題, 我們可以考慮同余最短路(同余最短路特征后邊再說)
我們發現剛才說的確實沒有什么問題, 神秘先輩告訴我們轉換稱圖論問題
瞪眼一看, 我們發現一個可行的 \(k\) 到另一個可行的 \(k\) 長得就像一個點通過有一個權值的邊到另一個點
想不想我們熟悉的
\(dis[v]=dis[u]+w\) ?
我們可以類比整出來
\(K_v=K_u+p (p\in \left \{a,b,c \right \} )\)
搞笑的是, 我們 \(h\) 的范圍太大了, 沒有辦法讓我們這么去搞
我們現在只需要加上我們最重要的一步
取模
通過找 \(x,y,z\) 中一個比較小的值(若差不多大就無所謂啦), 通過對這個值進行取模, 最后將取模過后的數最后一起計算, 我們就可以正確解決問題了
到這個例子, 我們可以做如下操作
我們選擇 \(x\) 做為上邊說的數字, 我們將\(\mod x\) 的各個 \(k\) 放到一起, 最后再統計答案的時侯直接一并計算
具體如下:
我們設 \(f(i)\) 代表我們使用隨便多少個 \(y\),\(z\) 所拼出來的 \(k\) 之中\(\mod x=i\) 的最小的一個 \(k\).
why如此設計?
我們固定了 \(y,z\), 從而可以算方案數, 我們可以將這個 \(f(i)\) 理解為使用 \(x\) 的"底線", 在對于每一個 \(i\) 計算方案的時侯, 我們就可以通過 \(\left \lfloor \frac{h-f(i)}{x} \right \rfloor + 1\) 來表示當前 \(i\) 的總方案數.
這樣我們就可以求解了
考慮一下怎么求出 \(f(i)\)?
我們上邊不是正好發現了 \(k\) 類似最短路的性質嗎?
加上取模我們不難列出如下式子
\(f(i)+y \ge f((i+y)\mod x)\)
\(f(i)+z \ge f((i+z)\mod x)\)
那我們將 \(i\) 與 \((i+y)\mod x\) 作為兩個點 連接上一條權值為 \(y\) 的單向邊
那同理將 \(i\) 與 \((i+z)\mod x\) 作為兩個點 連接上一條權值為 \(z\) 的單向邊
跑我們的 \(Dijkstra/Spfa\), 我們就得到了我們想要的 \(f(i)\).
我們然后就可以從 \(0\) 到 \(h-1\) 按上邊的方法求就可以了
代碼
粘一下, 個人碼風或許有些奇怪
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=3e6+316;
struct Node{
int nxt, to, w;
}node[MN];
int head[MN], tottt;
inline void insert(int u, int v, int w){
node[++tottt].to=v;
node[tottt].w=w;
node[tottt].nxt=head[u];
head[u]=tottt;
}
int dis[MN], vis[MN];
priority_queue <pair<int,int>> q;
void Dijkstra(int s){
for(int i=0; i<MN; ++i) dis[i]=0x3f3f3f3f3f3f3f3f;
memset(vis,0,sizeof(vis));
dis[s]=0; q.push({0,s});
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=node[i].nxt){
int v=node[i].to, w=node[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({-dis[v],v});
}
}
}return;
}
int h, x, y, z, ans=0;
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>h>>x>>y>>z; --h;
for(int i=0; i<x; ++i){
insert(i,(i+y)%x,y);
insert(i,(i+z)%x,z);
}
Dijkstra(0);
for(int i=0; i<x; i++)
if(h>=dis[i]) ans+=(h-dis[i])/x+1;
cout<<ans<<'\n';
return 0;
}
例題2.0
題意の簡述
$ {\textstyle \sum_{i=1}^{n}a_ix_i=b} $ 我們給定 \(a_i\) , 求有多少 \(b\in [l,r]\) 可以使這個等式存在非負整數解
我們已經知道了像上一道題那樣的題目可以使用同余最短路, 這個題無非就是多了一些 \(x,y,z\), 道理都一樣, 我們找一個最小的做模數, 然后向前邊這么做就行了, 對與 \([l,r]\) 我們像處理前綴和一樣將 \(ans(r)-ans(l-1)\) 就行了.
放一下代碼, 注意這個題有個 \(a_i\) 為 \(0\) 的 \(hack\).
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=5e6+316;
struct Node{
int nxt, to, w;
}node[MN];
int head[MN], tottt;
inline void insert(int u, int v, int w){
node[++tottt].to=v;
node[tottt].nxt=head[u];
node[tottt].w=w;
head[u]=tottt;
}
int dis[MN], vis[MN];
priority_queue <pair<int,int>> q;
void Dijkstra(int s){
for(int i=0; i<MN; ++i) dis[i]=LLONG_MAX;
memset(vis,0,sizeof(vis));
q.push({0,s}); dis[s]=0;
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=node[i].nxt){
int v=node[i].to, w=node[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({-dis[v],v});
}
}
}
}
int n, l, r, a[MN], minn=0x3f3f3f3f3f3f3f3f, mem=0;
int query(int x){
int res=0;
for(int i=0; i<minn; ++i){
if(x>=dis[i]) res+=((x-dis[i])/minn)+1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>l>>r;
for(int i=1; i<=n; ++i){
cin>>a[i]; if(!a[i]) continue;
if(a[i]<minn){
minn=a[i];
mem=i;
}
}
for(int i=0; i<minn; ++i){
for(int j=1; j<=n; ++j){
insert(i,(i+a[j])%minn,a[j]);
}
}
Dijkstra(0);
cout<<query(r)-query(l-1)<<'\n';
return 0;
}
題就先這樣, 給一下特征和練習
特征&練習
一般有以下特征
- 大范圍目標值
- 固定整數集合
- 線性組合形式(拼湊整數的存在性,計數或最小不可表示問題)
我個人覺得就是這個樣子吧......
再給一點題
浙公網安備 33010602011771號