Submission #1060555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060555		vjudge1	Subtree (INOI20_subtree)	C++14	12 / 100	688 ms	1048580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
ll n, m, pr[mxn], dp[mxn][2], mul[mxn<<1];
bool ck[mxn], vis[mxn];
vector<ll> cycle;
vector<vector<ll>> g(mxn);
void get_cycle(ll u, ll v)
{
    // cerr << u << '\n'; 
    cycle.pb(u); ck[u] = 1;
    if (u == v) return;
    get_cycle(pr[u],v);
}
void dfs(ll u, ll v)
{
    vis[u] = 1;
    for (ll i : g[u]) if (i != v) 
    {
        if (vis[i] && !cycle.size()) 
        {
            // cerr << u << ' ' << i << '\n';
            get_cycle(u,i);
        }
        else if (!vis[i])
        {
            pr[i] = u;
            dfs(i,u);
        }
    }
}
void dfs_dp(ll u, ll v)
{
    dp[u][1] = 1;
    for (ll i : g[u]) if (i != v && !ck[i])
    {
        dfs_dp(i,u);
        dp[u][1] *= dp[i][1]+1;
        dp[u][1] %= mod;
        dp[u][0] += (dp[i][0]+dp[i][1])%mod;
        if (dp[u][0] >= mod) dp[u][0] -= mod;
    }
}
ll bpow(ll a, ll b)
{
    if (!b) return 1;
    ll m = bpow(a,b/2);
    if (b&1) return (((m*m)%mod)*a)%mod;
    return (m*m)%mod;
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++)
    {
        ll a, b; cin >> a >> b;
        g[a].pb(b); g[b].pb(a);        
    }
    dfs(1,1);
    if (!cycle.size()) cycle.pb(1);
    for (ll i : cycle) dfs_dp(i,i);
    ll ans = 0, id = 0; mul[0] = 1;
    for (ll i : cycle)
    {
        ans += (dp[i][0]+dp[i][1])%mod;
        if (ans >= mod) ans -= mod;
        id++; mul[id] = dp[i][1];
    }
    n = cycle.size();
    for (ll i = n+1; i <= 2*n; i++) mul[i] = mul[i-n];
    for (ll i = 1; i <= 2*n; i++) mul[i] = (mul[i]*mul[i-1])%mod;
    queue<ll> q;
    ll s = 0;
    for (ll i = 0; i < n-2; i++) 
    {
        ll inv = bpow(mul[i],mod-2);
        q.push(inv); s += inv;
        if (s >= mod) s -= mod;
    }
    for (ll i = n-1; i <= 2*n-2; i++)
    {
        ans += (s*mul[i])%mod;
        if (ans >= mod) ans -= mod;
        s -= q.front(); q.pop();
        if (s < 0) s += mod;
        ll inv = bpow(mul[i-1],mod-2);
        q.push(inv); s += inv;
        if (s >= mod) s -= mod;
    }   
    cout << ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50