// OB会夏合宿2011 Day4 F : 影の魔女 #include #include #include #include #include using namespace std; typedef vector< vector > Matrix; Matrix mul(Matrix A, Matrix B){ int n = A.size(); Matrix res(n, vector(n,0)); for(int i=0;iabs(a[pivot][i])) pivot = j; swap(a[i], a[pivot]); double div = a[i][i]; for(int j=0;j<=n;j++) a[i][j] /= div; for(int j=i+1;j=0;i--) for(int j=0;j> S >> N >> K){ S = abs(S); if(N==1){ if(S%K==0) cout << S/K << endl; else cout << -1 << endl; continue; } for(int i=0;i<=K;i++) for(int j=0;j<=N*K;j++) prob[i][j] = 0; // K回でどれだけの距離進むかについて、確率を求める prob[0][0] = 1.0; for(int i=0;i > a(N*K, vector(N*K+1, 0)); a[0][0] = 1; for(int i=1;i=N*Kなら期待値はN*K項の漸化式で表せるので、行列積で期待値を求める else { Matrix A(N*K+1, vector(N*K+1,0)); for(int i=0;i