algospot - numb3rs

//numb3rs
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, D, P;
vector<vector<int>> adj;
vector<vector<double>> cache;
vector<int> Size;
 
void init()
{
    cin >> N >> D >> P;
    adj = vector<vector<int>>(N, vector<int>(N));
    cache = vector<vector<double>>(N, vector<double>(D + 1, -1));
    Size = vector<int>(N, 0);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            cin >> adj[i][j];
            if (adj[i][j])
                ++Size[i];
        }
}
 
double dp(int idx, int day)
{
    if (!day)
        return idx == P ? 1.0 : 0.0;
 
    double &ret = cache[idx][day];
    if (ret != -1)
        return ret;
    ret = 0;
    for (int i = 0; i < N; ++i)
        if (adj[i][idx])
            ret += dp(i, day - 1) / (double)Size[i];
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int C;
    cin >> C;
    cout << fixed;
    cout.precision(8);
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        int n; cin >> n;
        int idx;
        for(int i = 0; i<n; ++i)
        {
            cin >> idx;
            cout << dp(idx, D) << " ";
        }
        cout << "\n";
    }
}

 

 

 

 

 

 

https://www.algospot.com/judge/problem/read/NUMB3RS

algospot.com :: NUMB3RS

 

 

 

 

 

 

NUMB3RS

C(idx, day) : day번째 날에 idx마을에 있을 확률

 

 

<NUMB3RS 점화식>