結果

問題 No.767 配られたジャパリまん
ユーザー soraie_soraie_
提出日時 2023-04-04 09:59:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 808 ms / 2,000 ms
コード長 6,881 bytes
コンパイル時間 5,741 ms
コンパイル使用メモリ 294,800 KB
最終ジャッジ日時 2025-02-11 22:49:28
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef _DEBUG
#ifdef _SORAIE
#define _GLIBCXX_DEBUG
#endif
#endif

#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
//--------------------------------------------------------------------
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define overload4(_1,_2,_3,_4,name,...) name
#define rep1(n) for(ll _ThiS_WoNt_Be_usEd=0;_ThiS_WoNt_Be_usEd<(ll)n;++_ThiS_WoNt_Be_usEd)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define rep4(i,a,b,c) for(ll i=(ll)a;i<(ll)b;i+=(ll)c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)

#if defined(_SORAIE) && defined(_DEBUG)

#include <debug.hpp>

#else

#define debug(...) void(0);
#define koko void(0);
#define pass(...) void(0);

#endif

#define mp make_pair
#define mt make_tuple
#define ten(d) int64_t(1e##d)
void doset(int n){cout << fixed << setprecision(n);cerr << fixed << setprecision(n);}
struct asdfghjkl{asdfghjkl(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);doset(20);}} qwertyuiop;
using ll = long long;
using ld = long double;
using dou = double;
constexpr int inf = 1 << 30;
constexpr ll INF = 1LL << 61;
constexpr ld pi = 3.14159265358;
constexpr ll mod1 = 1000000007LL;
constexpr ll mod2 = 998244353LL;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
using pii = pair<int,int>;
template<class T, class U> inline bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
ll modpow(ll n,ll m,ll MOD){
    if(m == 0)return 1;
    if(m < 0)return 0;
    ll res = 1;
    n %= MOD;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}
ll mypow(ll n,ll m){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n);
        m >>= 1;
        n *= n;
    }
    return res;
}

inline bool isp(ll n){
    bool res = true;
    if(n == 1 || n == 0)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
inline bool Yes(bool b = 1){cout << (b ? "Yes\n":"No\n");return b;}
inline bool YES(bool b = 1){cout << (b ? "YES\n":"NO\n");return b;}
map<ll,ll> primefactor(ll n){
    map<ll,ll> ma;
    if(n <= 1)return ma;
    ll m = n;
    for(ll i = 2;i * i <= n;i++){
        while(m % i == 0){
            ma[i]++;
            m /= i;
        }
    }
    if(m != 1)ma[m]++;
    return ma;
}
vector<ll> divisor(ll n,bool sorted = true,bool samein = false){
    vector<ll> res;
    for(ll i = 1;i * i <= n;i++){
        if(n % i == 0){
            res.push_back(i);
            if(i * i != n || samein)res.push_back(n / i);
        }
    }
    if(sorted)sort(all(res));
    return res;
}

template<class T> inline void operator--(vector<T>& v) { for(int i = 0;i < int(v.size());i++)v[i]--; }
template<class T> inline void operator--(vector<T>& v,int) { for(int i = 0;i < int(v.size());i++)v[i]--; }

template<class T>
inline void pv(const vector<T>& v,const string& sep = " ",const string& end = "\n") {
    for(int i = 0;i < int(v.size());i++) cout << v[i] << (i == int(v.size()) - 1 ? end : sep);
}

#if __has_include("atcoder/all")
#include <atcoder/all>
using namespace atcoder;
template<class stream,int m>
stream& operator<<(stream& os,const static_modint<m>& mi){ return os << mi.val(); }
template<class stream,int m>
stream& operator<<(stream& os,const dynamic_modint<m>& mi){ return os << mi.val(); }
#endif

// #include <boost/multiprecision/cpp_dec_float.hpp>
// using lld = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<20>>;

// #include <boost/multiprecision/cpp_int.hpp>
// using lll = boost::multiprecision::cpp_int;

//--------------------------------------------------------------------

template<class T>
struct binomial{
    binomial(int n = 0):_fac(n + 10),_inv(n + 10),_finv(n + 10){
        _fac[0] = _inv[0] = _finv[0] = 1;
        _fac[1] = _inv[1] = _finv[1] = 1;
        for(int i = 2;i < n + 10;i++){
            _fac[i] = _fac[i - 1] * i;
            _inv[i] = T(i).inv();
            _finv[i] = _finv[i - 1] * _inv[i];
        }
    }
    void expand(int n){
        for(int i = _fac.size();i < n + 10;i++){
            _fac.push_back(_fac[i - 1] * i);
            _inv.push_back(T(i).inv());
            _finv.push_back(_finv[i - 1] * _inv[i]);
        }
    }
    T fac(int n){
        expand(n);
        return _fac[n];
    }
    T inv(int n){
        expand(n);
        return _inv[n];
    }
    T finv(int n){
        expand(n);
        return _finv[n];
    }

    T C(int n,int k){
        if(n < k || k < 0 || n < 0)return T(0);
        return fac(n) * finv(n - k) * finv(k);
    }
    T P(int n,int k){
        if(n < k || k < 0 || n < 0)return T(0);
        debug(n,fac(n),n-k,finv(n - k));
        return fac(n) * finv(n - k);
    }
    T H(int n,int k){
        if(n < 0 || k < 0)return T(0);
        return k == 0 ? T(1) : C(n + k - 1,k);
    }
private:
    std::vector<T> _fac,_inv,_finv;
};


int main() {
    using mint = static_modint<100'000'007>;
    int H,W,K;
    cin >> H >> W >> K;
    vector<int> A(K),B(K);
    rep(i,K)cin >> A[i] >> B[i];
    vector<mint> all_pass(1 << K);
    binomial<mint> bin(H + W);
    rep(i,1 << K){
        vector<pii> cur;
        rep(j,K){
            if(i >> j & 1)cur.emplace_back(A[j],B[j]);
        }
        sort(all(cur));
        int sz = cur.size();
        bool fl = 1;
        rep(j,sz - 1){
            if(cur[j].first < cur[j + 1].first && cur[j].second > cur[j + 1].second){
                fl = 0;
                break;
            }
        }
        if(!fl)continue;
        mint res = 1;
        pii now(0,0);
        rep(i,sz){
            int h = cur[i].first - now.first,w = cur[i].second - now.second;
            res *= bin.C(h + w,h);
            now = cur[i];
        }
        int h = H - now.first,w = W - now.second;
        res *= bin.C(h + w,h);
        all_pass[i] = res;
    }
    debug(all_pass);
    // sum(all_pass[k]) k&i==k,kの下からjbit以上はiと一致
    vector<vector<mint>> memo(1 << K,vector<mint>(K + 1));
    rep(i,1 << K){
        if(__builtin_popcount(i) & 1)memo[i][0] = -all_pass[i];
        else memo[i][0] = all_pass[i];
    }
    rep(j,K){
        rep(i,1 << K){
            if(i >> j & 1)memo[i][j + 1] += memo[i][j] + memo[i & ~(1 << j)][j];
            else memo[i][j + 1] = memo[i][j];
        }
    }
    debug(memo);
    rep(i,1 << K){
        cout << memo[i][K] << "\n";
        // if(__builtin_popcount(i) & 1)cout << -memo[i][K] << "\n";
        // else cout << memo[i][K] << "\n";
    }
}
0