洛谷P3306 隨機數生成器

2022-09-23 07:07:05 字數 1402 閱讀 2238

小w喜歡讀書,尤其喜歡讀《約翰克里斯朵夫》。最近小w準備讀一本新書,這本書一共有\(p\)頁,頁碼範圍為\(0 \cdots p-1\)。

小w很忙,所以每天只能讀一頁書。為了使事情有趣一些,他打算使用noi2012上學習的線性同餘法生成一個序列,來決定每天具體讀哪一頁。

我們用xi來表示通過這種方法生成出來的第\(i\)個數,也即小\(w\)第\(i\)天會讀哪一頁。這個方法需要設定\(3\)個引數\(a,b,x1\),滿足\(0\leq a,b,x1\leq p-1\),且\(a,b,x1\)都是整數。按照下面的公式生成出來一系列的整數:\(x_ \equiv ax_i+b \pmod p\)其中\(mod\)表示取餘操作。

但是這種方法可能導致某兩天讀的頁碼一樣。

小w要讀這本書的第\(t\)頁,所以他想知道最早在哪一天能讀到第t頁,或者指出他永遠不會讀到第\(t\)頁。

題目意思就是給你一個遞推式\(x_i=ax_+b\)和\(x_1\),讓你求一個最小的\(i\)使得\(x_i\equiv t \pmod p\)。

大力推柿子,容易得到

\[x_i=a^x_1+a^b+a^b+...+b

\]我們發現所有含有\(b\)的項是一個等比數列,所以可以用等比數列求和公式化簡。

\[x_i=a^x_1+\fracb-b}

\]也就是要求

\[t\equiv a^x_1+\fracb-b} \pmod p

\]在這個柿子中,只有\(a^\)是未知的。所以考慮化簡出\(a^\)。

\[t+\frac\equiv a^x_1+\fracb} \pmod p

\]\[t+\frac\equiv a^(x_1+\frac) \pmod p

\]所以

\[a^\equiv \frac}}\pmod p

\]\[a^\equiv \frac\pmod p

\]用\(bsgs\)求出\(i-1\)即可。

需要特判以下幾點:

當\(x_1=t\)時,答案就是1。

當\(a=0\)時,第一天已經在\((1)\)中特判了,從第二天起,頁碼都是\(b\)。所以如果\(b=t\)答案即為2,否則無解。

當\(a=1\)時

#include #include #include #include #include using namespace std;

typedef long long ll;

ll p,a,b,x1,t;

int t;

maphash;

ll power(ll x,ll k,ll mod)

ll bsgs()

return -2;

}int main()

else if (a==1)

else

}return 0;

}

洛谷P3600 隨機數生成器

題目連結 一個 n 個數的序列,裡面每個數值域為 1 x 。給 q 個區間,每個區間的權值為這段區間裡面的最小的數,然後算出了一個 ans min q i ,問 ans 的期望大小。 md,太久沒寫題了,菜的摳腳了已經。 官方題解寫的挺好的 刪除包含區間。 luogu3600 include inc...

洛谷P3600 隨機數生成器 期望dp 組合數

題目連結 一條重要的性質 如果某個區間覆蓋了另一個區間,那麼該區間是沒有用的 不會對最大值做出貢獻 首先不難想到列舉最終的答案 x 。這時我們需要計算的是最大值恰好為 x 的概率。 發現不是很好搞,我們記 p x 表示最大值 leqslant x 的概率,那麼恰好為 x 的概率為 p x p x 1...