ICPC 2019 Asia Yokohama Regional E Reordering the Documents

問題ページ
問題を整理すると，長さの数列を長さ以下の増加列に分解する方法が何通りあるか？となる． であるような が同じ増加列に属することはない．逆にこれ以外の についてはどのように増加列に振り分けても問題ない．

「上述のような をつないだグラフを白/黒の2色で塗り分ける．隣り合う頂点を違う色で塗る かつ 同じ色は個以下となる塗り方は何通りあるか？」という問題になった．もしグラフが二部グラフでないとすると，条件を満たす塗り方は存在しないので答えは0になる．グラフが二部グラフの場合，色の塗り方は各連結成分で2通りしかない．各連結成分でどちらの塗り方をするか？というDPを行うことで数え上げることができる．

番目の連結成分まで白色が個 何通りあるか というDPテーブルを持つ．番目の連結成分について，白・黒の頂点数が，であるとき，遷移は

• 白を個，黒を個
• 白を個，黒を個

となる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long int;  
using PII = pair<ll,ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
ll MOD = 1000000007;  
  
signed main() {  
    ll n, m;  
    cin >> n >> m;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    vector<vector<ll>> g(n);  
    REP(i, n) FOR(j, i+1, n) {  
        if(a[i] > a[j]) {  
            g[i].push_back(j);  
            g[j].push_back(i);  
        }  
    }  
  
    ll cnt0, cnt1;  
    vector<ll> col(n);  
    function<bool(ll,ll)> dfs = [&](ll v, ll c) {  
        if(c == -1) cnt0++;  
        else cnt1++;  
        col[v] = c;  
        for(auto to: g[v]) {  
            if(col[to] == c) return false;  
            if(col[to] == 0 && !dfs(to, -c)) return false;  
        }  
        return true;  
    };  
  
    vector<PII> v;  
    REP(i, n) {  
        if(col[i] == 0) {  
            cnt0 = cnt1 = 0;  
            bool ret = dfs(i, -1);  
            if(!ret) {  
                cout << 0 << endl;  
                return 0;  
            }  
            v.emplace_back(cnt0, cnt1);  
        }  
    }  
  
    const ll sz = v.size();  
    vector<ll> s(sz);  
    REP(i, sz) s[i] = v[i].first + v[i].second;  
    FOR(i, 1, sz) s[i] += s[i-1];  
  
    vector<vector<ll>> dp(sz+1, vector<ll>(m+1));  
    dp[0][0] = 1;  
    REP(i, sz) REP(j, m+1) {  
        if(j+v[i].first<=m && s[i]-j-v[i].first<=m) {  
            (dp[i+1][j+v[i].first] += dp[i][j]) %= MOD;  
        }  
        if(j+v[i].second<=m && s[i]-j-v[i].second<=m) {  
            (dp[i+1][j+v[i].second] += dp[i][j]) %= MOD;  
        }  
    }  
  
    ll ret = 0;  
    REP(i, m+1) (ret += dp[sz][i]) %= MOD;  
    cout << ret << endl;  
}