[ 题目描述]
现在有一个圆圈， 顺时针标号分别从 0 到 n-1， 每次等概率顺时针走一步或者逆时针走一步，
即如果你在 i 号点，你有 1/2 概率走到((i-1)mod n)号点，1/2 概率走到((i+1)mod n)号点。问
从 0 号点走到 x 号点的期望步数。
[ 输入]
第一行包含一个整数 T，表示数据的组数。
接下来有 T 行，每行包含两个整数 n, x。
T<=10, 0<=x<n<=300;
[ 输出]
对于每组数据，输出一行，包含一个四位小数表示答案。
[ 样例输入]
3
3 2
5 4
10 5
[ 样例输出]
2.0000
4.0000
25.0000
[ 数据范围]
对于 30% 的数据，n<=20
对于 50% 的数据，n<=100
对于 70% 的数据，n<=200
对于 100%的数据，n<=300
期望公式：
E[x]=0 (x==0);
E[x]=0.5*(E[x-1]+1)+0.5*(E[x+1]+1); (x!=0)
移项得，-E[i-1]*0.5+E[i]-E[i+1]*0.5=1
n 个方程高斯消元求解。
但有一个奇技淫巧
我们发现答案只有整数，于是打表，发现ans=(n-x)*x
%%%%%YZD佬orz
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
int T;
cin>>T;
while(T--)
{
int a,b;
cin>>a>>b;
cout<<b*(a-b)<<".0000"<<endl;
}
return ;
}
但这毕竟是奇技淫巧，还是上正解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double a[][];
int n;
int main()
{
int i,j,now,k,x,T;
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
cin>>T;
while (T--)
{
cin>>n>>x;
memset(a,,sizeof(a));
for (i=; i<=n-; i++)
{
if (i==x)
{
a[i+][i+]=;
a[i+][n+]=;
}
else
{
a[i+][i+]=;
a[i+][(i-+n)%n+]=a[i+][(i+)%n+]=-0.5;
a[i+][n+]=;
}
}
for (i=; i<=n; i++)
{
now=i;
for (j=i+; j<=n; j++)
if (fabs(a[now][i])<fabs(a[j][i]))
now=j;
for (j=i; j<=n+; j++)
swap(a[now][j],a[i][j]);
for (j=i+; j<=n+; j++)
a[i][j]/=a[i][i];
a[i][i]=;
for (j=i+; j<=n; j++)
{
for (k=i+; k<=n+; k++)
a[j][k]-=a[i][k]*a[j][i];
a[j][i]=;
}
}
for (i=n; i>=; i--)
{
for (j=i+; j<=n; j++)
{
a[i][n+]-=a[i][j]*a[j][n+];
a[i][j]=;
}
a[i][n+]/=a[i][i];
a[i][i]=;
}
printf("%.4lf\n",a[][n+]);
}
}