제출 #498030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498030		andrei_boaca	Star Trek (CEOI20_startrek)	C++17	100 / 100	138 ms	32112 KiB

startrek

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,d,nr[2][2],nrL,nrW,dp[100005][2][2],win[100005],rez[2][2],c[2][2],sol[2][2],parent[100005],nrlose[100005];
ll suma[100005][2][2];
vector<int> muchii[100005];
set<int> losers[100005];
bool use[100005];
void mult(ll a[2][2],ll b[2][2])
{
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
        {
            c[i][j]=0;
            for(int k=0;k<=1;k++)
                c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%mod)%mod;
        }
}
void matpw(ll b)
{
    while(b)
    {
        if(b&1)
        {
            mult(rez,nr);
            for(int i=0;i<=1;i++)
                for(int j=0;j<=1;j++)
                    rez[i][j]=c[i][j];
        }
        b/=2;
        mult(nr,nr);
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                nr[i][j]=c[i][j];
    }
}
void dfs(int nod,int par)
{
    parent[nod]=par;
    nrlose[nod]=0;
    win[nod]=0;
    for(int i:muchii[nod])
        if(i!=par)
        {
            dfs(i,nod);
            if(win[i]==0)
            {
                losers[nod].insert(i);
                nrlose[nod]++;
                win[nod]=1;
            }
        }
    for(int i:muchii[nod])
        if(i!=par)
        {
            for(int j=0;j<=1;j++)
                for(int k=0;k<=1;k++)
                    suma[nod][j][k]=(suma[nod][j][k]+dp[i][j][k])%mod;
            if(win[i]==0)
                nrlose[nod]--;
            if(nrlose[nod]==0)
            {
                dp[nod][0][1]=(dp[nod][0][1]+dp[i][1][1])%mod;
                dp[nod][0][0]=(dp[nod][0][0]+dp[i][1][0])%mod;
            }
            else
            {
                dp[nod][1][1]=(dp[nod][1][1]+dp[i][1][1])%mod;
                dp[nod][1][0]=(dp[nod][1][0]+dp[i][1][0])%mod;
            }
            dp[nod][1][1]=(dp[nod][1][1]+dp[i][0][1])%mod;
            dp[nod][1][0]=(dp[nod][1][0]+dp[i][0][0])%mod;
            if(win[i]==0)
                nrlose[nod]++;
        }
    if(nrlose[nod]==0)
    {
        dp[nod][1][0]++;
        dp[nod][1][0]%=mod;
        dp[nod][0][1]++;
        dp[nod][0][1]%=mod;
    }
    else
    {
        dp[nod][1][0]++;
        dp[nod][1][0]%=mod;
        dp[nod][1][1]++;
        dp[nod][1][1]%=mod;
    }
}
void recalc(int nod)
{
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            dp[nod][i][j]=0;
    if(nrlose[nod]>0)
        win[nod]=1;
    else
        win[nod]=0;
    if(nrlose[nod]>1)
    {
        dp[nod][1][1]=(suma[nod][1][1]+suma[nod][0][1])%mod;
        dp[nod][1][0]=(suma[nod][1][0]+suma[nod][0][0])%mod;
    }
    if(nrlose[nod]==1)
    {
        int lose=*losers[nod].begin();
        dp[nod][1][1]=(suma[nod][1][1]+suma[nod][0][1])%mod;
        dp[nod][1][1]-=dp[lose][1][1];
        if(dp[nod][1][1]<0)
            dp[nod][1][1]+=mod;
        dp[nod][1][0]=(suma[nod][1][0]+suma[nod][0][0])%mod;
        dp[nod][1][0]-=dp[lose][1][0];
        if(dp[nod][1][0]<0)
            dp[nod][1][0]+=mod;
        dp[nod][0][1]=dp[lose][1][1];
        dp[nod][0][0]=dp[lose][1][0];
    }
    if(nrlose[nod]==0)
    {
        dp[nod][0][0]=suma[nod][1][0];
        dp[nod][0][1]=suma[nod][1][1];
        dp[nod][1][0]=suma[nod][0][0];
        dp[nod][1][1]=suma[nod][0][1];
    }
    if(nrlose[nod]==0)
    {
        dp[nod][1][0]++;
        dp[nod][1][0]%=mod;
        dp[nod][0][1]++;
        dp[nod][0][1]%=mod;
    }
    else
    {
        dp[nod][1][0]++;
        dp[nod][1][0]%=mod;
        dp[nod][1][1]++;
        dp[nod][1][1]%=mod;
    }
}
void reroot(int par,int fiu)
{
    if(win[fiu]==0)
    {
        nrlose[par]--;
        losers[par].erase(fiu);
    }
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
        {
            suma[par][i][j]-=dp[fiu][i][j];
            if(suma[par][i][j]<0)
                suma[par][i][j]+=mod;
        }
    recalc(par);
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
        {
            suma[fiu][i][j]+=dp[par][i][j];
            if(suma[fiu][i][j]>=mod)
                suma[fiu][i][j]-=mod;
        }
    if(win[par]==0)
    {
        nrlose[fiu]++;
        losers[fiu].insert(par);
    }
    recalc(fiu);
}
void calcdp(int nod)
{
    use[nod]=1;
    for(int i:muchii[nod])
        if(!use[i])
        {
            reroot(nod,i);
            int root=i;
            for(int k=0;k<=1;k++)
                for(int j=0;j<=1;j++)
                {
                    nr[j][k]=(nr[j][k]+dp[root][k][j]);
                    if(nr[j][k]>=mod)
                        nr[j][k]-=mod;
                }
            if(win[root]==0)
                nrL++;
            if(win[root]==1)
                nrW++;
            calcdp(i);
            reroot(i,nod);
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int root=1;root<=1;root++)
    {
        for(int i=1;i<=n;i++)
        {
            win[i]=0;
            for(int j=0;j<=1;j++)
                for(int k=0;k<=1;k++)
                    dp[i][j][k]=0;
        }
        dfs(root,0);
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
            {
                nr[j][i]=(nr[j][i]+dp[root][i][j]);
                if(nr[j][i]>=mod)
                    nr[j][i]-=mod;
            }
        if(win[root]==0)
            nrL++;
        if(win[root]==1)
            nrW++;
        if(root==1)
        {
            for(int i=0;i<=1;i++)
                for(int j=0;j<=1;j++)
                    sol[i][j]=dp[root][i][j];
        }
    }
    calcdp(1);
    rez[0][0]=nrL;
    rez[0][1]=nrW;
    if(d>1)
        matpw(d-1);
    ll ans=(sol[1][0]*rez[0][0])%mod;
    ans=(ans+sol[1][1]*rez[0][1]%mod)%mod;
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15