補程式碼:
#include <cstdio>
#include <algorithm>
using namespace std;
int m;
struct Matrix { double p[50][50]; };
Matrix Mul(const Matrix &a, const Matrix &b)
{
Matrix c;
int x, y, z;
for (y=0; y<m; y++)
for (x=0; x<m; x++)
for (z=0, c.p[y][x]=0; z<m; z++)
c.p[y][x]+=a.p[y][z]*b.p[z][x];
return c;
}
int main()
{
int t, n, s, x, y, bit;
double ans;
Matrix a, b;
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &s);
if (s<=n)
{
puts("100.0%");
continue;
}
if (s>=n+m)
{
puts("0.0%");
continue;
}
for (y=0; y<m; y++)
for (x=0; x<m; x++)
{
a.p[y][x] = ( x==y ? 1.0 : 0.0 );
if (x==0) b.p[y][x]=1.0/m;
else if (x==y+1) b.p[y][x]=1.0;
else b.p[y][x]=0.0;
}
for (bit=1; bit<=n; bit<<=1)
{
if (n&bit) a=Mul(a, b);
b=Mul(b, b);
}
for (y=s-n, ans=0.0; y<m; y++) ans+=a.p[y][0];
printf("%.1lf%%\n", ans*100);
}
return 0;
}