P5007 但模数的疑惑

省流： $answer \bmod 10^8+7$ 。

现有题解好像都没有认真讲转移式怎么来的，我来写一下。

显然设

f_u

为子树内价值和，

w_u

为

u

的点权，由于需要知道集合数才能转移，再设

g_u

为子树内集合数。

f_u

的转移：

已考虑的子树和目前子树内所有集合组合： $f_u\times g_v$
已考虑的子树内所有集合和目前子树组合： $g_u\times f_v$
不取目前子树集合： $f_u$
只取目前子树集合： $f_v$
综上： $f_u\to f_u\times g_v+g_u\times f_v+f_u+f_v$

g_u

的转移：

已考虑的子树内所有集合和目前子树集合组合 $g_u\times g_v$
不取目前子树集合： $g_u$
只取目前子树集合： $g_v$
综上： $g_u\to g_u\times g_v+g_u+g_v$

注意到只取

u

也是一种情况，在最后令

f_u\to f_u+w_u,g_u\to g_u+1

即可。

答案显然为

f_1

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5,mod=1e9+7;
int n,t,u,v;
ll f[N],g[N],w[N];
vector<int> G[N];
void dfs(int u,int fa){
    for(int v:G[u]){
        if(v==fa) continue;
        dfs(v,u);
        f[u]=(f[u]*g[v]+f[v]*g[u]+f[u]+f[v])%mod;
        g[u]=(g[u]*g[v]+g[u]+g[v])%mod;
    }
    (f[u]+=w[u])%mod;
    g[u]++;
}
int main(){
    cin>>n>>t;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        w[i]=t*(i-1)+1;
    dfs(1,1);
    cout<<f[1];
    return 0;
}

P5007 但模数的疑惑

文章操作

省流： $answer \bmod 10^8+7$ 。

相关推荐

评论

P5007 但模数的疑惑

文章操作

省流：answer mod 108+7answer \bmod 10^8+7answermod108+7。

相关推荐

评论

省流： $answer \bmod 10^8+7$ 。