Module

Input the first row which includes a positive integer n, n is within 10³, to represent the number of test points; and a positive integer m, m is within 10⁹, to represent the number of test machines; and a positive integer k, k is within 10¹⁸ to represent test times.

The second row has n integers, A₀,A₁,…,A_n-1, which represent the number of test machines each test point deployed to.

C++14(g++5.4) 解法, 执行用时: 688ms, 内存消耗: 616K, 提交时间: 2019-07-25 23:57:32

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long

const double eps=1e-8;
const ll inf=1e9;
const ll mod=1e9+7;
const int maxn=1e3+10;

/**
每个数都选一遍，最后除以m
[ f[i-1][j-1]+(f[i-1][j]*m-f[i-1][j]) ]/m

-f[i-1][j] 数j各有一次被选中

**/

double a[maxn];
int n;

struct mat
{
    double a[maxn];
    mat()
    {
        memset(a,0,sizeof(a));   ///一定要，不知道为什么
    }
    void init()
    {
        a[0]=1;
    }
    mat operator*(const mat &y) const
    {
        mat z;
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                z.a[(i+j)%n]+=a[i]*y.a[j];
        return z;
    }
};

mat mul(mat a,ll b)
{
    mat y;
    y.init();
    while (b)
    {
        if (b&1)
            y=y*a;
        a=a*a;
        b>>=1;
    }
    return y;
}

int main()
{
//    FILE *in=fopen("data.in","r");
//    FILE *out=fopen("data.out","w");
    ll m,k,i,j;
    mat ori,y;
    double tot;
//    fscanf(in,"%lld%lld%lld",&n,&m,&k);
    scanf("%lld%lld%lld",&n,&m,&k);
    for (i=0;i<n;i++)
//        fscanf(in,"%lf",&a[i]);
        scanf("%lf",&a[i]);

//    ori.a[0]=1-1.0/m;
//    ori.a[n-1]=1.0/m;

    ori.a[0]=1.0-1.0/m;
    ori.a[1]=1.0/m;

    y=mul(ori,k);

    for (i=0;i<n;i++)
    {
        tot=0;
        for (j=0;j<n;j++)
            tot+=y.a[j]*a[(i-j+n)%n];
//            tot+=y.a[(j-i+n)%n]*a[j];
//        fprintf(out,"%.1f%c",tot,i==n-1?'\n':' ');
        printf("%.1f%c",tot,i==n-1?'\n':' ');
    }
//    fclose(in);
//    fclose(out);
    return 0;
}
/*
2 3 1
3 0
*/

C++11(clang++ 3.9) 解法, 执行用时: 937ms, 内存消耗: 23904K, 提交时间: 2019-04-22 22:06:14

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn=1002;
struct node
{
    double t[maxn][maxn];
}a,b,r;
void cheng2(node &cnt,const node &A,const node &B,ll n)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cnt.t[i][j]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cnt.t[0][i]+=A.t[0][j]*B.t[j][i];
	}
}
void cheng1(node &cnt,const node &A,const node &B,ll n)
{
	cheng2(cnt,A,B,n);
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<n;j++)
		{
			cnt.t[j][(i+j)%n]=cnt.t[0][i];
		}
	}
}
int main()
{
    long long n,m,K;
	cin>>n>>m>>K;
    for(int i=0,x;i<n;i++)
    {
        cin>>x;
        a.t[0][i]=x;
    }
    for(int i=0;i<n;i++)
    {
        b.t[i][i]=1.0*(m-1)/m;
        b.t[(i-1+n)%n][i]=1.0/m;
    }
   	while(K)
    {
        if(K&1)
		{
			cheng2(r,a,b,n);
			a=r;
		}
		cheng1(r,b,b,n);
		b=r; 
		K/=2;
    }
    for(int i=0;i<n;i++)
    	printf("%.1lf ",a.t[0][i]);
    return 0;
}

详情