Darth Vader and Tree

CodeForces - 514E

When Darth Vader gets bored, he sits down on the sofa, closes his eyes and thinks of an infinite rooted tree where each node has exactly n sons, at that for each node, the distance between it an its i-th left child equals to di. The Sith Lord loves counting the number of nodes in the tree that are at a distance at most x from the root. The distance is the sum of the lengths of edges on the path between nodes.

But he has got used to this activity and even grew bored of it. 'Why does he do that, then?' — you may ask. It's just that he feels superior knowing that only he can solve this problem.

Do you want to challenge Darth Vader himself? Count the required number of nodes. As the answer can be rather large, find it modulo 109 + 7.

Input

The first line contains two space-separated integers n and x (1 ≤ n ≤ 105, 0 ≤ x ≤ 109) — the number of children of each node and the distance from the root within the range of which you need to count the nodes.

The next line contains n space-separated integers di (1 ≤ di ≤ 100) — the length of the edge that connects each node with its i-th child.

Output

Print a single number — the number of vertexes in the tree at distance from the root equal to at most x.

Examples

Input
3 3
1 2 3
Output
8

Note

Pictures to the sample (the yellow color marks the nodes the distance to which is at most three)

给出一个每个节点有n个孩子的多叉树，父亲到第i个孩子有固定的长度，问到根节点的距离不超过x的节点的数目。
1 <= n <= 1e5; 0 <= x <= 1e9; 1 <= di <= 100 Mod=1e9+7

sol：有一个较显然的dp,dp[i]表示深度为i的点的个数，这样就有了一个很裸的暴力

/*

给出一个每个节点有n个孩子的多叉树，父亲到第i个孩子有固定的长度，问到根节点的距离不超过x的节点的数目。

1 <= n <= 1e5; 0 <= x <= 1e9; 1 <= di <= 100  Mod=1e9+7

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=; bool f=; char ch=' ';

    while(!isdigit(ch))    {f|=(ch=='-'); ch=getchar();}

    while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<) {putchar('-'); x=-x;}

    if(x<) {putchar(x+''); return;}

    write(x/); putchar((x%)+'');

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const ll N=,Mod=;

ll n,m,d[N];

ll dp[N],f[];

inline void Ad(ll &x,ll y)

{

    x+=y; x-=(x>=Mod)?Mod:;

}

int main()

{

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

    int i,j,k;

    R(n); R(m);

    for(i=;i<=n;i++) f[d[i]=read()]++; sort(d+,d+n+); n=unique(d+,d+n+)-d-;

    dp[]=;

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

    {

        for(j=;j<=min(i,);j++) Ad(dp[i],dp[i-j]*f[j]%Mod);

    }

    ll ans=;

    for(i=;i<=m;i++) Ad(ans,dp[i]);

    Wl(ans);

    return ;

}

然后发现di很小，转移方程可以用矩阵快速幂优化，发现转移dp[x]时有用的就是dp[x-100]~dp[x],而在转移dp[x+1]时有用的就是dp[x-99]~dp[x+1]了，而转移就是向暴力写的dp一样，每次只要转移最后一位就是了，前面的都可以搬过来，所以矩阵就可以推了

[0 0 0 ... 0 0 f[100] f[100]]
[1 0 0 ... 0 0 f[99] f[99]    ]
[0 1 0 ... 0 0 f[98] f[98]    ]
[0 0 1 ... 0 0 f[97] f[97]    ]
...
[0 0 0 ... 0 1 f[1] f[1]        ]
[0 0 0 ... 0 0 0 1              ]

/*

给出一个每个节点有n个孩子的多叉树，父亲到第i个孩子有固定的长度，问到根节点的距离不超过x的节点的数目。

1 <= n <= 1e5; 0 <= x <= 1e9; 1 <= di <= 100  Mod=1e9+7

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=; bool f=; char ch=' ';

    while(!isdigit(ch))    {f|=(ch=='-'); ch=getchar();}

    while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<) {putchar('-'); x=-x;}

    if(x<) {putchar(x+''); return;}

    write(x/); putchar((x%)+'');

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const ll N=,Mod=;

ll n,m,dp[N],f[N],Qzh[N];

ll a[N][N],b[N][N],c[N][N],ans[N][N];

inline void Ad(ll &x,ll y)

{

    x+=y; x-=(x>=Mod)?Mod:;

}

int main()

{

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

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

    int i,j,k;

    R(n); R(m);

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

    dp[]=Qzh[]=;

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

    {

        for(j=;j<=i;j++) Ad(dp[i],dp[i-j]*f[j]%Mod);

        Qzh[i]=Qzh[i-]; Ad(Qzh[i],dp[i]);

    }

    if(m<=)

    {

        Wl(Qzh[m]); return ;

    }

//    for(i=0;i<=100;i++) W(dp[i]); puts("");

    for(i=;i<=;i++) ans[][i]=dp[i]; ans[][]=Qzh[];

    for(i=;i<=;i++) a[i][i]=;

    for(i=;i<=;i++) b[i][i-]=; b[][]=;

    for(i=;i<=;i++) b[i][]=b[i][]=f[-i];

//    for(i=1;i<=101;i++,puts("")) for(j=1;j<=101;j++) W(b[i][j]);

//    memmove(b,a,sizeof b);

    int oo=m-;

    while(oo)

    {

        if(oo&)

        {

            memset(c,,sizeof c);

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

            {

                Ad(c[i][j],1ll*a[i][k]*b[k][j]%Mod);

            }

            memmove(a,c,sizeof a);

        }

        oo>>=;

        memset(c,,sizeof c);

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

        {

            Ad(c[i][j],1ll*b[i][k]*b[k][j]%Mod);

        }

        memmove(b,c,sizeof b);

    }

    memset(c,,sizeof c);

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

    {

        Ad(c[i][j],ans[i][k]*a[k][j]%Mod);

    }

    memmove(ans,c,sizeof ans);

    Wl(ans[][]);

    return ;

}

最新文章

  1. Sql Server中不常用的表运算符之APPLY(2)
  2. centos python2.6 升级到 python2.7
  3. Android--ViewPager制作APP引导页
  4. poj 题目分类(3)
  5. [LeetCode#161] One Edit Distance
  6. T4模板_根据DB生成实体类
  7. 在web应用程序中使用MemcachedClient
  8. Dubbo（一） 开始认识Dubbo，分布式服务框架
  9. 学unity3d需要什么基础
  10. Linux下网站根目录权限
  11. 分布式事务2PC_PENDING异常处理
  12. iOS----------developerDiskImage
  13. 打造SharePoint之在线开发神器SPOnlineDevelopTool（一）——概述
  14. 漏洞扫描，linux配置规范处理
  15. CORS跨域
  16. SharePoint REST API - 同步SharePoint列表项
  17. Python 映射
  18. jquery中的全选、反选、全不选和单删、批删
  19. 什么是SEO服务，企业为什么要做SEO？
  20. Internet History, Technology and Security (Week 5-1)

热门文章

  1. 在论坛中出现的比较难的sql问题：25(字符串拆分3)
  2. 使用Harbor搭建Docker私有镜像仓库
  3. md5 helper
  4. 【转载】C#使用FirstOrDefault方法快速查找List集合中符合条件的第一个实体
  5. JS权威指南读书笔记（二）
  6. MD 使用 i5ting_toc 转换成 HTML
  7. sql server 2012 分页/dapper/C#拼sql/免储存过程/简易
  8. javascript 箭头函数的使用 初学者必看
  9. Cknife流量分析
  10. STM32 HAL库学习系列第8篇---回调函数总结