有n + 2个座位等距地排成丐排，从左到右编号为0至n + 1
初始时0号以及n + 1号座位上已经坐了一个小G，接下来会有n个小G依次找一个空座位坐下
由于小G们坐得太近就容易互相搏弈，每个小G会找一个位置，使得离当前最近的小G距离最远
如果有多个备选的座位，这个小G会等概率选择其中一个
给出n，求第i个坐下的小G坐在j号座位的概率, 对P取模
一看到这题就想到打表……
其实感觉正解也不难想的样子
但既然教练说不用改那就不改吧……emmmm
放一下最后打出来的表
dalao们肯定可以看出规律的！
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,mod;
ll gcd(ll a,ll b)
{
if(!b) return a;
return gcd(b,a%b);
}
struct Fenshu
{
ll fm,fz;
Fenshu operator * (const Fenshu &a) const
{
Fenshu tmp=*this;
tmp.fm*=a.fm;
tmp.fz*=a.fz;
ll g=gcd(tmp.fm,tmp.fz);
tmp.fm/=g;
tmp.fz/=g;
return tmp;
}
}dp[1030][1030],test[5];
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
ll qpow(ll n,ll k)
{
ll res=1;
while(k)
{
if(k&1) res=(res*n)%mod;
n=(n*n)%mod;
k>>=1;
}
return res;
}
ll inv(ll x) {return qpow(x,mod-2);}
int main()
{
freopen("seat.in","r",stdin);
freopen("seat.out","w",stdout);
read(n);read(mod);
if(n==1)
{
puts("1");
return 0;
}
else if(n==2)
{
ll ans=inv(2);
for(register int i=1;i<=2;++i) printf("%lld ",ans);
puts("");
for(register int i=1;i<=2;++i) printf("%lld ",ans);
return 0;
}
else if(n==3)
{
puts("0 1 0");
ll ans=inv(2);
cout<<ans<<" 0 "<<ans<<endl;
cout<<ans<<" 0 "<<ans<<endl;
}
else if(n==4)
{
ll two=inv(2);
ll thr=inv(3);
ll six=inv(6);
cout<<"0 "<<two<<" "<<two<<" 0"<<endl;
cout<<thr<<" "<<six<<" "<<six<<" "<<thr<<endl;
cout<<thr<<" "<<six<<" "<<six<<" "<<thr<<endl;
cout<<thr<<" "<<six<<" "<<six<<" "<<thr<<endl;
}
else if(n==5)
{
ll two=inv(2);
ll fou=inv(4);
cout<<"0 0 1 0 0"<<endl;
for(register int i=1;i<=4;++i)
cout<<fou<<" "<<fou<<" 0 "<<fou<<" "<<fou<<endl;
}
else if(n==6)
{
ll two=inv(2);
ll fou=inv(4);
ll eig=inv(8);
cout<<"0 0 "<<inv(2)<<" "<<inv(2)<<" 0 0"<<endl;
cout<<"0 "<<inv(2)<<" 0 0 "<<inv(2)<<" 0"<<endl;
for(register int i=1;i<=4;++i)
cout<<inv(4)<<" "<<inv(8)<<" "<<inv(8)<<" "<<inv(8)<<" "<<inv(8)<<" "<<inv(4)<<endl;
}
else if(n==7)
{
ll two=inv(2);
ll fou=inv(4);
ll eig=inv(8);
cout<<"0 0 0 1 0 0 0"<<endl;
cout<<"0 "<<two<<" 0 0 0 "<<two<<" 0"<<endl;
cout<<"0 "<<two<<" 0 0 0 "<<two<<" 0"<<endl;
for(register int i=1;i<=4;++i)
cout<<fou<<" 0 "<<fou<<" 0 "<<fou<<" 0 "<<fou<<endl;
}
else if(n==8)
{
ll two=inv(2);
ll thr=inv(3);
ll six=inv(6);
ll twl=inv(12);
ll fiv=inv(5);
ll twe=inv(20);
ll ten=inv(10);
cout<<"0 0 0 "<<two<<" "<<two<<" 0 0 0"<<endl;
cout<<"0 "<<thr<<" "<<six<<" 0 0 "<<six<<" "<<thr<<" 0"<<endl;
cout<<"0 "<<5*twl%mod<<" "<<twl<<" 0 0 "<<twl<<" "<<5*twl%mod<<" 0"<<endl;
for(register int i=1;i<=5;++i)
cout<<fiv<<" "<<twe<<" "<<3*twe%mod<<" "<<ten<<" "<<ten<<" "<<3*twe%mod<<" "<<twe<<" "<<fiv<<endl;
}
else if(n==9)
{
ll fou=inv(4);
ll six=inv(6);
ll twl=inv(12);
cout<<"0 0 0 0 1 0 0 0 0"<<endl;
cout<<"0 "<<fou<<" "<<fou<<" 0 0 0 "<<fou<<" "<<fou<<" 0"<<endl;
cout<<"0 "<<fou<<" "<<fou<<" 0 0 0 "<<fou<<" "<<fou<<" 0"<<endl;
for(register int i=1;i<=6;++i)
cout<<six<<" "<<twl<<" "<<twl<<" "<<six<<" 0 "<<six<<" "<<twl<<" "<<twl<<" "<<six<<endl;
}
else if(n==10)
{
ll two=inv(2);
ll fou=inv(4);
ll sev=inv(7);
ll esb=inv(28);
ll xxx=(3*esb)%mod;
ll sss=inv(14);
cout<<"0 0 0 0 "<<two<<" "<<two<<" 0 0 0 0"<<endl;
cout<<"0 0 "<<two<<" 0 0 0 0 "<<two<<" 0 0"<<endl;
cout<<"0 "<<fou<<" "<<fou<<" 0 0 0 0 "<<fou<<" "<<fou<<" 0"<<endl;
for(register int i=1;i<=7;++i)
cout<<sev<<" "<<xxx<<" "<<esb<<" "<<sev<<" "<<sss<<" "<<sss<<" "<<sev<<" "<<esb<<" "<<xxx<<" "<<sev<<endl;
}
return 0;
}