Submission #82347

#	Time	Username	Problem	Language	Result	Execution time	Memory
82347		MrTEK	Tents (JOI18_tents)	C++14	48 / 100	238 ms	223976 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 3e2 + 5;
const int mod = 1e9 + 7;

int n,m,ans,fac[N],inv[N],dp[N][N][N],dp2[N][N],pw[N];

inline int mul(int x,int y) {
  return (ll) x * y % mod;
}

inline int add(int x,int y) {
  return (x + y) % mod;
}

int fast_pow(int x,int y) {
  if (y == 0)
    return 1;
  int res = fast_pow(x,y / 2);
  res = mul(res,res);
  if(y & 1)
    res = mul(res,x);
  return res;
}

inline int comb(int n,int r) {
  return mul(fac[n],mul(inv[n - r],inv[r]));
}


int g(int x,int y) {
  int &res = dp2[x][y];
  if (x == 0 || y == 0)
    return 1;
  if (res != -1)
    return res;
  res = g(x,y - 1);
  if (x >= 1)
    res = add(res,mul(x * 2,g(x - 1,y - 1)));
  if (x >= 2)
    res = add(res,mul(x * (x - 1) / 2,g(x - 2,y - 1)));
  return res;
}

int f(int t,int x,int y) {
  int &res = dp[t][x][y];
  if (x == 0)
    return res = g(n - t,y);
  if (res != -1)
    return res;
  res = 0;
  if (y >= 2)
    res = add(res,mul(y * (y - 1) / 2,f(t,x - 1,y - 2)));
  if (y >= 1)
    res = add(res,mul(2 * y,f(t,x - 1,y - 1)));
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m;
  pw[0] = inv[0] = fac[0] = 1;
  for (int i = 1 ; i <= max(n,m) ; i++) {
    fac[i] = mul(fac[i - 1],i);
    pw[i] = mul(pw[i - 1],2);
    inv[i] = fast_pow(fac[i],mod - 2);
  }
  memset(dp,-1,sizeof dp);
  memset(dp2,-1,sizeof dp2);
  for (int i = 0 ; i <= n ; i++)
    ans = add(ans,mul(comb(n,i),f(i,i,m)));
  cout << ans - 1 << endl;
}

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52