题意：给定 a,b,p a , b , p 求 ax=b (mod p) a x = b ( m o d p ) 的最小正整数解， p p 为质数，保证有解。
显然 x<px<p。令 t=p–√ t = p ， 如果我们能找到一组 (c,d) ,0<=d<t ( c , d ) , 0 <= d < t ，使得：
(at)c=b⋅ad ( a t ) c = b · a d 那么 x x 就等于 c⋅t−dc·t−d。 我们把 b⋅ai(0<=i<t) b · a i ( 0 <= i < t ) 放在一个哈希表里，然后枚举 c c ，在表里找。 复杂度 O(n−−√)O(n)设 (a,m)=1 ( a , m ) = 1 满足 ar=1 (mod m) a r = 1 ( m o d m ) 的最小正整数解称作 a a 模 mm 的阶。 如果整数 a a 模 mm 的阶为 ϕ(m) ϕ ( m ) 那么称 a a 是模 mm 的原根。 计算原根：由于原根一般不会很大，我们可以枚举原根 a a ，判断 aa 的阶是不是 ϕ(n) ϕ ( n ) 。
推论：原根 g g 的 0,1,…,ϕ(p)0,1,…,ϕ(p) 次方构成模 p p 的一个缩系。
题意：给定 p,k,ap,k,a（ p p 是质数）,求所有满足 xk=a (mod p)xk=a (mod p) 的 x x 。
令 gg 为 p p 的原根,则 xx 可以表示为: gz g z ， a a 可以表示为 gbgb:
xzk=gb (mod p) x z k = g b ( m o d p ) 两边同取离散对数: z⋅k=b (mod p−1) z · k = b ( m o d p − 1 ) 解线性同余方程。条件概率： P(B|A)=P(A⋂B)P(B) P ( B | A ) = P ( A ⋂ B ) P ( B ) 无论两随机变量是否独立，期望的线性性始终成立。
题意： n n 个点的有根树，每个点是白色的，每次等概率选择一个点染黑，并且把它子树里的点都染黑。求把整颗树染黑的期望次数。
貌似不是很好做… 换个角度，整颗树染黑以后，每个点被选中的概率。 一个点被染黑，当且仅当它的一个祖先或他自己被染黑。并且他们是等概率的。 由于选中代价是1，所以期望就是概率。 因此答案为: ∑i1deep[i]∑i1deep[i]
题意：给定 n n 种物品，每次购买会随机买到一种，询问买到 nn 种物品的期望次数。
考虑我们已经买到了 k k 种物品，再继续买多少次能得到第 k 1k 1 种物品。 设它为 x x ，则： x=(1−k/n)⋅(x 1) k/n⋅1x=(1−k/n)·(x 1) k/n·1 整理得：
x=1(1−k/n) x = 1 ( 1 − k / n ) 那么答案就是 n∑ni=11n n ∑ i = 1 n 1 n如果某件事发生的概率为 p p ，那么发生这件事的期望次数是 1p1p
POJ[2069] 题意：一个软件有 s s 个子系统，会产生 nn 种bug。某人每天发现一个bug，每个bug属于某个子系统的概率是 1/s 1 / s ，属于某种分类的概率是 1/n 1 / n 。问发现 n n 种bug，且每个子系统都发现bug的天数的期望。
设 f[i][j]f[i][j] 表示已经找到了 i i 种分类，jj 种bug，还需要的期望天数。
f[i][j]=f[i][j+1]⋅in⋅s−js+f[i+1][j]⋅n−in⋅js+f[i+1][j+1]⋅n−in⋅s−js+f[i][j]⋅in⋅js+1 f [ i ] [ j ] = f [ i ] [ j + 1 ] · i n · s − j s + f [ i + 1 ] [ j ] · n − i n · j s + f [ i + 1 ] [ j + 1 ] · n − i n · s − j s + f [ i ] [ j ] · i n · j s + 1题意：初始有 k k 只生物，这种生物只能活一天，死的时候有 pipi 的概率产生 i i 只新生物（也只能活一天），询问 mm 天后所有生物都死的概率（包括 m m 天前死的情况）。
首先观察到每只生物是独立的，所以我们可以分开计算，最后 kk 次方。 设 f[i] f [ i ] 表示 i i 天后所有生物都死的概率。转移的时候枚举第一天它产了几个子： f[i]=∑j=0n−1f[i−1]j⋅pjf[i]=∑j=0n−1f[i−1]j·pj 答案是 f[m]k f [ m ] k
BZOJ[1419] 题意：有 n n 张 1 1和 m m 张−1−1，可以中途停止拿牌，询问按照最优策略拿牌，最后的得分期望。
设 f[i][j] f [ i ] [ j ] 表示还有 i i 张 1 1和 j j 张−1−1的得分期望。显然满足最优子结构性质。转移的时候如果期望小于 0 0 就不拿了。 f[i][j]=max(0,(f[i][j−1]−1)⋅ji j (f[i−1][j] 1)⋅ii j)f[i][j]=max(0,(f[i][j−1]−1)·ji j (f[i−1][j] 1)·ii j)
题意：要求摆放 n n 块骨牌，但排放时会有 plpl 的概率使它左边所有挨着它的骨牌倒下，同理，右边的概率为 pr p r ，询问摆完 n n 块的期望次数。
设 f[i]f[i] 表示摆放连续 i i 个骨牌的期望次数。 转移的时候枚举 ii 这个骨牌放在哪里。如果设摆好左边的期望次数为 E1 E 1 ，右边为 E2 E 2 。 f[i] f [ i ] 就等于期望往左边倒的次数 ×E1+ × E 1 + 期望往右边倒的次数 ×E2+ × E 2 + 不倒的期望次数 +E1+E2 + E 1 + E 2 根据前面讲的，不倒的期望次数就是不倒的概率的倒数 11−pl−pr 1 1 − p l − p r 。也就是说，前面的 11−pl−pr−1=pl+pr1−pl−pr 1 1 − p l − p r − 1 = p l + p r 1 − p l − p r 次都是往左或者往右倒的（很玄妙）。 那么，往左倒的期望次数就是 pl+pr1−pl−pr∗plpl+pr=pl1−pl−pr p l + p r 1 − p l − p r ∗ p l p l + p r = p l 1 − p l − p r ，右边同理。 因此，我们可以得到：
f[i]=pl1−pl−pr⋅E1+pr1−pl−pr⋅E2+11−pl−pr+E1+E2 f [ i ] = p l 1 − p l − p r · E 1 + p r 1 − p l − p r · E 2 + 1 1 − p l − p r + E 1 + E 2[NOI2015]聪聪和可可 题意：给定无向图，两个点A,B，每次A都向着离B最近的方向走，如果两个点都可以，走编号小的那个。A如果走一次没有遇到，可以接着再走一次。B每次等概率地走到相邻的点或待在原地，求A遇上B的期望时间。
设 f[i][j] f [ i ] [ j ] 表示A在 i i ，B在 jj 的答案。
f[i][j]=1+∑(j,k)∈E|k=jf[pos(i,j)][k]d[j]+1 f [ i ] [ j ] = 1 + ∑ ( j , k ) ∈ E | k = j f [ p o s ( i , j ) ] [ k ] d [ j ] + 1 pos(i,j) p o s ( i , j ) 表示A在 i i ，B在 jj，下一步A的位置。因此我们需要预处理最短路，预处理 pos p o s ，然后一波记忆化搜索。 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #define ll long long using namespace std; struct edge{ int to,next; }ed[1000010]; double f[1100][1100]; int du[1100],dis[1100][1100],path[1100][1100],head[1100],sz,vis[1100][1100]; inline void add(int from,int to) { ed[++sz].to=to; ed[sz].next=head[from]; head[from]=sz; } inline void read(int &x) { char c=getchar();x=0;int flag=1; while(!isdigit(c)) { if(c=='-') flag=-1; c=getchar(); } while(isdigit(c)) x=x*10+c-'0',c=getchar(); x*=flag; } double dfs(int A,int B) { if(f[A][B]!=-1) return f[A][B]; if(A==B) return f[A][B]=0; if(path[A][B]==B||path[path[A][B]][B]==B) return f[A][B]=1; f[A][B]=0; int pos=path[path[A][B]][B]; for(int i=head[B];i;i=ed[i].next) { int v=ed[i].to; f[A][B]+=dfs(pos,v); } f[A][B]+=dfs(pos,B); f[A][B]/=(1.0*(du[B]+1)); f[A][B]+=1; return f[A][B]; } inline void dij(int s) { queue <int> q; q.push(s); vis[s][s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=ed[i].next) { int v=ed[i].to; if(!vis[s][v]) { dis[s][v]=dis[s][u]+1; vis[s][v]=1; q.push(v); } } } } int main() { int n,m,A,B; read(n),read(m),read(A),read(B); for(int i=1;i<=m;i++) { int u,v; read(u),read(v); add(u,v),add(v,u); du[u]++,du[v]++; } for(int i=1;i<=n;i++) dij(i); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) continue; int ind=0,Min=1e9; for(int k=head[i];k;k=ed[k].next) { int v=ed[k].to; if(dis[v][j]<Min||(dis[v][j]==Min&&v<ind)) { Min=dis[v][j]; ind=v; } } path[i][j]=ind; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=-1; printf("%.3lf",dfs(A,B)); return 0; }