codeforces 514E-Darth Vader and Tree

题意：有个无限大的有根树,每个节点都有N个孩子,每个孩子距离父亲节点的距离为di.求距离根节点距离<=x的节点个数.

思路：注意观察数据范围，每一个d[i]均小于等于100所以我们可以设dp[i]表示距离原点i的点的个数，sum[i]表示总和，最后求sum[x]即可。

状态转移方程

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

     {

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

         {

             dp[i]=(dp[i]+dp[i-j]*cnt[j])%MOD;

         }

         sum[i]=(sum[i-]+dp[i])%MOD;

     }

但是因为x太大，而且dp[n+1]是每个dp[i]*cnt[n+1-i]，令N=100，保存n+1前100个数，并用第101列更新sum，用矩阵快速幂求解即可。（C是单位矩阵！！！）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll MOD=(ll)1e9+;

 struct matrix

 {

     ll x,y;

     ll a[][];

     matrix(){

     };

     matrix(ll xx,ll yy):x(xx),y(yy)

     {

         memset(a,,sizeof(a));

     }

 }Base;

 matrix mul (matrix A,matrix B)

 {

     matrix C(A.x,B.y);

     for(int i=;i<=A.x;i++)

     {

         for(int j=;j<=B.y;j++)

         {

             for(int k=;k<=B.x;k++)

             {

                 C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;

             }

         }

     }

     return C;

 }

 ll n,x,cnt[],sum[],dp[];

 void init()

 {

     memset(cnt,,sizeof(cnt));

     scanf("%lld%lld",&n,&x);

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

     {

         int p;

         scanf("%d",&p);

         cnt[p]++;

     }

     memset(sum,,sizeof(sum));

     dp[]=; sum[]=;

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

     {

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

         {

             dp[i]=(dp[i]+dp[i-j]*cnt[j])%MOD;

         }

         sum[i]=(sum[i-]+dp[i])%MOD;

     }

     Base.x=; Base.y=;

     //123...97 98 99  100 101(ans)

     //000...000 len[100] len[100]

     //100...000 len[99] len[99]

     //010...000 len[98] len[98]

     //.........................

     //000...001 len[1] len[1]

     //000...000 0        1

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

     {

         Base.a[i+][i]=;

         Base.a[i][]=cnt[-i];

         Base.a[i][]=cnt[-i];

     }

     Base.a[][]=Base.a[][]=cnt[];

     Base.a[][]=;

 }

 matrix qpow (matrix Base,ll b)

 {

     matrix C(Base.x,Base.y);

     for(int i=;i<=;i++) C.a[i][i]=;//danweijuzhen

     while(b)

     {

         if(b%==) C=mul(C,Base);

         b/=;

         Base=mul(Base,Base);

     }

     return C;

 }

 int main()

 {

     init();

     matrix A(,);

     for(int i=;i<=;i++) A.a[][i]=dp[i];

     A.a[][]=sum[];

     if(x<=)

     {

         printf("%lld\n",sum[x]);

         return ;

     }

     A=mul(A,qpow(Base,x-));

     printf("%lld\n",A.a[][]%MOD);

     return ;

 }

巴特西

codeforces 514E-Darth Vader and Tree

最新文章

热门文章