Submission #18296197

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>
#include <bitset>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

ll div(ll& d, int x) {
    ll ret = 0;
    while(d % x == 0) {
        ++ret;
        d /= x;
    }
    return ret;
}

void solve() {
    ll n, d;
    cin >> n >> d;
    ll n2 = div(d, 2);
    ll n3 = div(d, 3);
    ll n5 = div(d, 5);
    if(d > 1) {
        cout << 0.0 << endl;
        return;
    }
    using vvld = vector<vld>;
    using vvvld = vector<vvld>;
    vvvld dp(n2+1, vvld(n3+1, vld(n5+1, 0.0)));
    dp[0][0][0] = 1.0;
    while(n--) {
        vvvld dp2(n2+1, vvld(n3+1, vld(n5+1, 0.0)));
        rep(i, n2+1) rep(j, n3+1) rep(k, n5+1) {
            ll i1 = min(i+1, n2);
            ll i2 = min(i+2, n2);
            ll j1 = min(j+1, n3);
            ll k1 = min(k+1, n5);
            ld add = dp[i][j][k] / 6.0;
            dp2[i][j][k] += add;
            dp2[i1][j][k] += add;
            dp2[i][j1][k] += add;
            dp2[i2][j][k] += add;
            dp2[i][j][k1] += add;
            dp2[i1][j1][k] += add;
        }
        dp = dp2;
    }
    cout << dp[n2][n3][n5] << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Submission Info

Judge Result