\(\mathcal{Description}\)

给定一个无并列语句的多重循环，每个变量取值的左端点只能是 \(1\) 或已定义的变量；右端点只能是 \(n\) 或已定义的变量。求循环语句关于 \(n\) 的复杂度以及常数。

循环语句数量 \(m<20\)。

\(\mathcal{Solution}\)

按变量的偏序关系建图，缩掉 SCC——它们的取值必然相等，设有 \(s\) 个 SCC，那么循环的复杂度显然是 \(\mathcal O(n^s)\)，难点在于求常数。

第一步转化是平凡的：我们可以钦定变量间的严格偏序而忽略取等的情况。这是因为当某两个变量取等时，不会对计算次数的最高次产生贡献。此外，我们还能得知在变量都取 \([1,n]\)，但被限制偏序时，一共有 \(s!\binom{n}{s}\) 种取值组。

第二步，利用缩点得到的 DAG 的性质，可以发现：在严格偏序意义下，满足 DAG 限制的变量组数量等于对 DAG 拓扑排序的方案数。 证明是平凡的。设方案数为 \(c\)，由此可知 \(\frac{c}{s!}\) 即循环的常数因子。

求解复杂度为 \(\mathcal O(2^mm^2)\)，瓶颈是状压求拓扑方案数。也许能优化 awa。（

\(\mathcal{Code}\)

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

typedef long long LL;

inline void chkmin( int& u, const int v ) { v < u && ( u = v ); }

inline LL gcd( const LL u, const LL v ) { return v ? gcd( v, u % v ) : u; }

const int MAXN = 20;

int n, adj[MAXN + 5], vad[MAXN + 5], ref[256];

int scc, dfc, dfn[MAXN + 5], low[MAXN + 5], bel[MAXN + 5];

LL f[1 << MAXN];

inline void tarjan( const int u ) {

    static int stk[MAXN + 5], top;

    static bool instk[MAXN + 5];

    instk[stk[++top] = u] = true, dfn[u] = low[u] = ++dfc;

    rep ( v, 0, n - 1 ) if ( adj[u] >> v & 1 ) {

        if ( !dfn[v] ) tarjan( v ), chkmin( low[u], low[v] );

        else if ( instk[v] ) chkmin( low[u], dfn[v] );

    }

    if ( dfn[u] == low[u] ) {

        int v;

        do instk[v = stk[top--]] = false, bel[v] = scc; while ( v != u );

        ++scc;

    }

}

int main() {

    freopen( "fygon20.in", "r", stdin );

    freopen( "fygon20.out", "w", stdout );

    scanf( "%d%*c", &n ), --n;

    if ( !n ) return puts( "0 1/1" ), 0;

    rep ( i, 0, n - 1 ) {

        static char str[200]; int st = i << 2;

        scanf( "%[^\n]%*c", str ), ref[str[st + 4]] = i;

        if ( str[st + 15] != '1' ) adj[i] |= 1 << ref[str[st + 15]];

        if ( str[st + 18] != 'n' ) adj[ref[str[st + 18]]] |= 1 << i;

    }

    rep ( i, 0, n - 1 ) if ( !dfn[i] ) tarjan( i );

    rep ( u, 0, n - 1 ) rep ( v, 0, n - 1 ) {

        if ( adj[u] >> v & 1 && bel[u] != bel[v] ) {

            vad[bel[u]] |= 1 << bel[v];

        }

    }

    f[0] = 1;

    rep ( S, 0, ( 1 << scc ) - 2 ) {

        rep ( u, 0, scc - 1 ) if ( ~S >> u & 1 ) {

            bool flg = true;

            rep ( v, 0, scc - 1 ) {

                flg &= !( v != u && ~S >> v & 1 && vad[v] >> u & 1 );

                if ( !flg ) break;

            }

            if ( flg ) f[S | 1 << u] += f[S];

        }

    }

    LL fac = 1;

    rep ( i, 1, scc ) fac *= i;

    LL d = gcd( fac, f[( 1 << scc ) - 1] );

    printf( "%d %lld/%lld\n", scc, f[( 1 << scc ) - 1] / d, fac / d );

    return 0;

}

巴特西

Solution -「NWRRC 2017」「洛谷 P7024」Fygon 2.0

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章