2017北京国庆刷题Day4 afternoon

期望得分：100+100+0=200

实际得分：5+0+0=5

每加入一个数，x的因数位置++

注意：根号x枚举时，如果x是完全平方数，根号x会重复累计2次，要减去

考场上没减，5分 /(ㄒoㄒ)/~~

#include<cmath>

#include<cstdio>

#include<iostream>

using namespace std;

#define N 40001

int sum[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

int main()

{

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

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

    int n,ans=;

    read(n);

    int x,y,z;

    while(n--)

    {

        read(x); read(y);

        if(x==)

        {

            z=sqrt(y);

            for(int i=;i<=z;i++)

                if(y%i==) sum[i]++,sum[y/i]++;

            if(z*z==y) sum[z]--;

        }

        else ans^=sum[y];

    }

    printf("%d",ans);

}

树形DP

令col[i] 表示 i与i的父节点之间的连边

f[i] 表示在节点i的子树中，链的一个端点为i，且与i直接相邻的边的边的颜色不与col[i] 相同的方案数

F[i] 表示对应的权值和

g[i] 表示在节点i的子树中，链的一个端点为i 的方案数

G[i] 表示对应的权值和

将i的子树中经过i的链分为两种

① 以i为端点，用 g G 统计

②i为中间的一个点，用 f F 统计

状态转移方程：

设j为i的子节点,val[i]表示节点i的点权

① g[i]=Σ（f[j]+1） G[i]=Σ（F[j]+val[j]）

② f[i]= Σ（f[j]+1） F[i]=Σ（F[j]+val[j]）其中，j满足col[j]!=col[i]

③ G[i]+=g[i]*val[i]

④ F[i]+=f[i]*val[i]

解释：

1、g[i]、f[i] 的转移就是把子树中的 g，f 累加起来，再加上子树的个数，因为i和i的子树的根节点（即i的子节点）构成一条新的合法的链

2、①、② 中 G、F 的转移就是把子树中的 G、F累加起来，再加上子节点的权值和，因为i和的i的子节点构成一条新的合法的链

3、③、④ 所有的以i为一个端点的链都累加一个 i的权值

统计答案：

1、以i为端点的链，就是ans+=G[i]

2、以i为中间一个点的链，显然是要拿以i为端点的两条链拼起来

①对于i的每个子树j，假设j会被使用sum次，子树j的合法链的权值总和为V，那么这个子树j 对答案的贡献就是 sum*（V+val[j]）。

加val[j]是因为子树j的根节点的权值不属于V，但以这个点为链的一个端点，以i的其他子树的一个点为链的另一个端点，这就是一条合法的链

如何统计sum？

设s[k]表示当前i的子树中，以i为链的一个端点且与i直接相连的边的颜色为k 的链的条数

颜色编号大至1e9？ ——离散化

那么sum=g[i]-s[col[j]] 即只要与i直接相连的边的颜色不等于 col[j] ，就可以与j的子树中的链以及 j 拼接

　 ② 考虑了链的拼接，还差两条链的交点的权值没有加，即i的权值。

设两条链拼接的总方案数位 tot，那么最后再加上 tot*val[i] 就行了

tot=Σ （ (f[[j]+1) * (g[i]-s[col[j]]) ） / 2 原理同上

除2是因为一条链被枚举了两次

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

int val[N];

int front[N],to[N<<],nxt[N<<],tot,col[N<<];

int has[N];

LL f[N],s[N],F[N];

LL ans;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar();  }

} 

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; col[tot]=w;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; col[tot]=w;

}

void init()

{

    int n;    read(n);

    for(int i=;i<=n;i++) read(val[i]);

    int u,v,c;

    for(int i=;i<n;i++)

    {

        read(u); read(v); read(c);

        has[i]=c;

        add(u,v,c);

    }

    sort(has+,has+n+);

    int tot=unique(has+,has+n+)-(has+);

    for(int i=;i<=n-<<;i++) col[i]=lower_bound(has+,has+tot+,col[i])-has;

}

void dfs(int x,int y,int z)

{

    int num=;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=y) num++,dfs(to[i],x,col[i]);

    LL g=,G=;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=y)

        {

            if(col[i]!=z) f[x]+=f[to[i]]+,F[x]+=F[to[i]]+val[to[i]];

            g+=f[to[i]]+,G+=F[to[i]]+val[to[i]];

            s[col[i]]+=f[to[i]]+;

        }

    if(!num) return;

    F[x]+=1ll*f[x]*val[x];

    G+=1ll*g*val[x];

    ans+=G;

    LL res=,tmp=;

    for(int i=front[x];i;i=nxt[i])

         if(to[i]!=y) res+=(F[to[i]]+val[to[i]])*(g-s[col[i]]),tmp+=(+f[to[i]])*(g-s[col[i]]);

    ans+=res+tmp/*val[x];

    for(int i=front[x];i;i=nxt[i]) s[col[i]]=;

}

int main()

{

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

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

    init();

    dfs(,,);

    printf("%I64d\n",ans);

}

解决本题关键：
同一行/列只有被选中奇数次才有效

假设有i行j列被翻了过来

那么可以得到等式

i*m+j*n-2*i*j=s

解得j=（s-i*m）/（n-2*i）

由此可知，我们只需要枚举i，就可以直接算出j

这个 i，j 合法的条件是：

① 不越界

②（n-i）%2=0，（m-j）%2=0

因为只能再翻偶数次，才能保证当前i，j 合法

如何计算一对合法的i，j的答案？

n行里i行被翻了过来 C（n，i）

m列里j列被翻了过来 C（m，j）

被翻了偶数次的行，就是把（r-i）/2 次机会分给 n 行 C（（r-i）/2+n-1，n-1）

注意不是n行里面选（r-i）/2 行翻过来，因为同一行可以不翻，也可以翻多次

同理，偶数次列为 C（（c-i）/2+m-1，m-1）

把这4个C 乘起来就是这一对i，j 的答案

最后累加所有的i，j 的贡献即可

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 200001

typedef long long LL;

const int mod=1e9+;

LL inv[N],fac[N];

LL pow(LL a,int b)

{

    LL res=;

    for(;b;a=a*a%mod,b>>=)

        if(b&) res*=a,res%=mod;

    return res;

}

int main()

{

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

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

    int n,m,r,c; LL s;

    scanf("%d%d%d%d%I64d",&n,&m,&r,&c,&s);

    fac[]=;inv[]=;

    for(int i=;i<=max(n,m)+max(r,c);i++) fac[i]=i*fac[i-],fac[i]%=mod,inv[i]=pow(fac[i],mod-);

    int j;

    int ans=; LL res;

    for(int i=(r&);i<=min(r,n);i+=)

    {

        if(n!=*i)

        {

            if((s-1ll*i*m)%(n-*i)) continue;

            j=(s-1ll*i*m)/(n-*i);

            if(j< || j>min(c,m) || (c-j)&) continue;

            res=fac[n]*inv[i]%mod*inv[n-i]%mod;

            res=res*fac[m]%mod*inv[j]%mod*inv[m-j]%mod;

            res=res*fac[n+(r-i>>)-]%mod*inv[n-]%mod*inv[r-i>>]%mod;

            res=res*fac[m+(c-j>>)-]%mod*inv[m-]%mod*inv[c-j>>]%mod;

            ans+=res; ans%=mod;

            //printf("%d %d %I64d\n",i,j,res);

        }

    }

    printf("%d",ans);

}

巴特西

2017北京国庆刷题Day4 afternoon

最新文章

热门文章