No.140 みんなで旅行 - yukicoder
class TravelTogether {
public:
void solve(void) {
int N;
cin>>N;
vector<vector<ll>> F(N+1,vector<ll>(N+1,-1));
vector<vector<ll>> C(N+1,vector<ll>(N+1,0));
REP(n,N)
{
C[n][0] = 1;
REP(r,N)
(C[n+1][r+1] = (C[n][r+1] + C[n][r]) % Mod) %= Mod;
}
function<ll(int,int)> f = [&](int x, int y) {
if (F[x][y] >= 0)
return F[x][y];
if (x==0 && y==0)
return F[x][y] = 1;
if (x < y || y <= 0)
return F[x][y] = 0;
return F[x][y] = (f(x-1,y-1) + y*f(x-1,y)% Mod) % Mod;
};
REP(x,N+1)
REP(y,N+1)
f(x,y);
ll res = 0;
REP(x,N+1)
REP(y,N+1)
{
ll tmp = C[N][x];
(tmp *= F[x][y]) %= Mod;
(tmp *= mpow(y*(y-1)%Mod, N-x)) %= Mod;
(res += tmp) %= Mod;
}
cout<<res<<endl;
}
};