Submission #456275

#	Time	Username	Problem	Language	Result	Execution time	Memory
456275		Dakto	Tents (JOI18_tents)	C++17	100 / 100	1801 ms	35756 KiB

tents

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DEBUGMODE 1
#ifdef ONLINE_JUDGE
#define DEBUGMODE 0
#endif

#define cerr if(DEBUGMODE) cerr
#define DEBUG(a) if(DEBUGMODE) cout<<(a)<<endl
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define EACH(i,c) for(auto (i):c)
#define endl '\n'
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define LLM LONG_LONG_MAX
#define gcd __gcd
#define pb push_back
#define pm make_pair
#define MANY_TESTS ll ntests; cin>>ntests; for(ll test=1; test<=ntests; test++) 
#define contains(a,b) ((a).find(b)!=(a).end())
#define INF 1e16
#define NINF -1e16
#define cinv(n,v) ll n; cin>>n; vl v(n); cin>>v;
#define fact(f,n) vl f={0}; for(ll i=0; i<n; i++) f.push_back(f[i]*(i+1));
#define codejamout(s) cout<<"Case #"<<test<<": "<<s<<"\n";
#define LOG(x) cerr<<"Line "<<__LINE__<<":"<<#x<<" = "<<x<<endl;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll,ll>> vpll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll MOD=1e9+7;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << ";" << par.second << ")"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }

template<typename T>
pair<T, ll> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<typename T>
pair<T, ll> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return {*it, it - v.begin()};}        
template<class T>
bool remin(T& a, const T& b){return (b<a?a=b,1:0);}
template<class T>
bool remax(T& a, const T& b){return (a<b?a=b,1:0);}

ll getbit(ll number, ll index){return (number & (1<<index))<<index;}


template <int MOD=1'000'000'007>
struct ModInt {
  int value;
  static const int MOD_value = MOD;

  ModInt(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  ModInt(long long a, long long b) : value(0){ *this += a; *this /= b;}

  ModInt& operator+=(ModInt const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  ModInt& operator-=(ModInt const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  ModInt& operator*=(ModInt const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend ModInt mexp(ModInt a, long long e) {
    ModInt res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend ModInt inverse(ModInt a) { return mexp(a, MOD - 2); }

  ModInt& operator/=(ModInt const& b) { return *this *= inverse(b); }
  friend ModInt operator+(ModInt a, ModInt const b) { return a += b; }
  friend ModInt operator-(ModInt a, ModInt const b) { return a -= b; }
  friend ModInt operator-(ModInt const a) { return 0 - a; }
  friend ModInt operator*(ModInt a, ModInt const b) { return a *= b; }
  friend ModInt operator/(ModInt a, ModInt const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, ModInt const& a) {return os << a.value;}
  friend bool operator==(ModInt const& a, ModInt const& b) {return a.value == b.value;}
  friend bool operator!=(ModInt const& a, ModInt const& b) {return a.value != b.value;}
};


int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    ll h,w;
    cin>>h>>w;

    vector<vector<ModInt<>>> dp(w+5,vector<ModInt<>>(h+5,0));

    dp[0][0]=1;

    REP(i,w+1){
        REP(j,h+1){
            dp[i+1][j]+=dp[i][j];
            dp[i+1][j+2]+=dp[i][j]*(h-j)*(h-j-1)/2;
            dp[i+1][j+1]+=dp[i][j]*(h-j)*4;
            dp[i+2][j+1]+=dp[i][j]*(h-j)*(i+1);
        }
    }

    ll res=0;
    REPR(i,1,h+1){
        res+=dp[w][i].value;
    }

    cout<<res%MOD<<endl;

    
    return 0;
}

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