No title

Anonymous Coward 2018-03-07 19:59:24.003549 UTC

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define fs first
#define sc second
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<pii> vpii;
typedef tuple<int, int, int> iii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag,
    tree_order_statistics_node_update> ost;

const int N=7;
const int M=8;
const int M2N=1<<21;
const double EPS=1e-8;
int f[M2N][N], mask[M2N], cnt[M];
double p[M], q[M];

int main() {
    int i, j, m, n, m2n;
    double v, d;
    scanf("%d%d", &n, &m);
    if(m==1) return printf("1.0000\n"), 0;
    n--;
    for(m2n=1, i=0; i<n; i++) m2n*=m;
    for(i=0; i<m2n; i++) {
        if(i>0) {
            for(j=0; j<n; j++) f[i][j]=f[i-1][j];
            for(j=0; f[i][j]==m-1; j++);
            f[i][j]++;
            for(j--; j>=0; j--) f[i][j]=0;
        }
        for(j=0; j<m; j++) cnt[j]=0;
        for(j=0; j<n; j++) cnt[f[i][j]]++;
        for(j=0; j<m; j++) if(cnt[j]==1) break;
        for(j--; j>=0; j--) if(cnt[j]==0) mask[i]|=1<<j;
    }
    for(i=0; i<m; i++) p[i]=1.0/m;
    for(;;) {
        for(i=0; i<m; i++) q[i]=0;
        for(i=0; i<m2n; i++) {
            v=1;
            for(j=0; j<n; j++) v*=p[f[i][j]];
            for(j=0; j<m; j++) if((mask[i]>>j)&1) q[j]+=v;
        }
        v=0;
        for(i=0; i<m; i++) v+=q[i];
        for(i=0; i<m; i++) q[i]/=v;
        d=0;
        for(i=0; i<m; i++) {
            d=max(d, abs(q[i]-1.0/m));
            p[i]=p[i]+0.5*(q[i]-1.0/m);
        }
        if(d<EPS) break;
    }
    for(i=0; i<m; i++) printf("%.12lf\n", abs(p[i]));
    return 0;
}