标签：int res 猎人 P2104 st 1ll sloj mod
题目大意：
- \(n\) 个猎人编号为 \(1, 2, \cdots, n\) 依次按逆时针方向排成一个环。
- 第一枪由你打响，你会向第 \((k - 1) \bmod n + 1 (k>0)\) 号猎人开枪，这个被击中的猎人有 \(\frac 1 2\) 的概率会死亡。所有被击中的猎人（无论死活），都会继续向他的逆时针方向开始的第 k kk 个（从他自己的下一个开始数）活着的猎人开枪。
- 当只剩一个人时游戏停止，无论最后射向他的子弹是否会打死他。
- 作为编号为 \(1\) 的猎人，想知道自己活到最后的概率。
算法分析：
- 我们很容易想到从终止状态倒推。
- 为了方便我们从 \(0\) 开始编号。
- 可以设计状态 \(f(i,j)\) 表示还剩 \(i\) 个人，其中 \(0\) 号在其中，并且编号为 \(0\)，上一枪射中了 \(j\)，\(0\) 号能存活到最后的概率。
- 答案即为 \(f(n,(k-1)\bmod n)\)。
- 不难根据被射中的这个人是否被打死了，然后转移：
\[\begin{align*}
f(i,j) =
\begin{cases}
\frac{1}{2}(f(i,(i+k) \mod i)+f(i-1,(i+k-1) \mod i) &(i \neq 0))\\
\frac{1}{2}f(i,(i+k) \mod i) &(i = 0)
\end{cases}
\end{align*}
\]
- 这里的转移形成了分层图，i − 1 i-1i−1 到 i ii 可以直接转移，但是 i ii 层之内的转移形成了若干个环，如果直接用高斯消元，时间复杂度为 \(\mathcal O(n^4)\)。
- 但是我们发现对于环的形式的转移，可以 \(\mathcal O(n)\) 实现。
- 对于一个环，我们考虑将所有的数表示为 \(k_ix+b_i\) 的形式，其中 \(x\) 是环中的指定一个值，然后 \(k_i,b_i\) 都是常数，这样我们可以利用这些表达式，把 \(x*\)* 也表达成 \(k′x+b′\)，解方程 \(x = k′x+b′\) 即可。
- 所以时间复杂度优化到 \(\mathcal O(n^2)\)。
#include <bits/stdc++.h>
#define mod 1000000007
#define N 2010
#define inv ((mod+1)>>1)
using namespace std;
int n,k,a[N],b[N],t[N],f[N][N],ne[N];
bool vis[N];
int qpow(int x,int y){
int res = 1;
for(;y;y>>=1,x = 1ll*x*x%mod)
if(y&1) res = 1ll*res*x%mod;
return res;
}
int main(){
scanf("%d%d",&n,&k);
f[1][0] = 1;
for (int i = 2;i<=n;i++){
for (int j = 0;j<i;j++){
vis[j] = false;
ne[(j+k)%i] = j;
if(j==0) t[j] = 0;
else t[j] = 1ll*inv*f[i-1][(j+k-1)%(i-1)]%mod;
}
for (int st = 0;st<i;st++){
if(vis[st]) continue;
int u = st;
a[st] = 1;
b[st] = 0;
vector<int>s;
for(;!vis[u];u = ne[u]){
vis[u] = true;
int v = ne[u];
if(v!=st) s.push_back(v);
a[v] = 1ll*a[u]*inv%mod;
b[v] = (1ll*b[u]*inv+t[v])%mod;
}
f[i][st] = 1ll*(mod-b[st])*qpow(a[st]-1,mod-2)%mod;
for(auto v : s) f[i][v] = (1ll*a[v]*f[i][st]+b[v])%mod;
}
}
printf("%d",f[n][(k-1)%n]);
return 0;
}
标签：int,
res,
猎人,
P2104,
st,
1ll,
sloj,
mod
From： https://www.cnblogs.com/cztq/p/17501085.html