BZOJ1195:[HNOI2006]最短母串 AC自动机+状压dp

思路:

首先我的思路十分傻叉,是\(f[i][j][k]\)表示长度为\(i\),在自动机上的节点为\(j\),包含子串的状态为\(k\)可不可能.但这样复杂度直接爆炸.

但是我们可以令\(f[i][j]\)表示在自动机上的节点为\(i\),包含子串的状态为\(j\)时的最短长度.

这样我们就转化成了边权均为1的单源最短路,BFS就行了.

若按照字母字典序从小到大的顺序进行BFS,得出的就是字典序最小的答案了.

(有点卡内存)

(话说我一开始AC自动机都写错,没治了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 12
#define L 610
 
short ch[L][26],end[L],pre[L],cnt;
 
char s[L];
 
int q[L],fr,ta;
short lastchar[L*(1<<N)];
int laststate[L*(1<<N)];
short state[L*(1<<N)];
short ins[L*(1<<N)];
bool vis[L][1<<N];
 
char ans[L];int id;
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int p,y;
    for(i=1;i<=n;++i){
        scanf("%s",s);int len=strlen(s);
        for(p=j=0;j<len;++j){
            if(!ch[p][y=s[j]-'A'])ch[p][y]=++cnt;p=ch[p][y];
        }end[p]|=1<<(i-1);
    }
    for(j=0;j<26;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<26;++j)if(ch[u][j]){
            for(q[ta++]=v=ch[u][j],r=pre[u];r&&!ch[r][j];r=pre[r]);end[v]|=end[pre[v]=ch[r][j]];
        }
        else ch[u][j]=ch[pre[u]][j];
    }
    int mask;
    for(fr=ta=0,state[0]=ins[0]=0,++ta;fr^ta;){
        u=ins[fr],mask=state[fr];
        if(mask==(1<<n)-1){
            for(;fr;fr=laststate[fr])ans[++id]=lastchar[fr];
            for(i=id;i>=1;--i)putchar('A'+ans[i]);
            return 0;
        }
        for(j=0;j<26;++j)if(!vis[ch[u][j]][mask|end[ch[u][j]]]){
            lastchar[ta]=j,laststate[ta]=fr,ins[ta]=ch[u][j],state[ta]=mask|end[ch[u][j]];
            vis[ins[ta]][state[ta]]=1;
            ta++;
        }++fr;
    }
    return 0;
}

BZOJ1043:[HAOI2008]下落的圆盘 计算几何+离线处理

思路:

嗯,我诅咒你,出题人,持续一辈子的呦~~

我们考虑每个圆对于最终答案的贡献,显然就是将所有在之后的圆覆盖在这个圆上的部分去掉,剩下的若干段弧长.

那么接下来就是找出对于一个圆,他有哪些部分是被覆盖的.

我们对于每一个后面的圆,找出他覆盖在这个圆上面的极角序区间,最后我们再求一次区间的并就可以了.

找出这段区间成为了这道题目的难点.

首先我们找出两个圆的交点.什么你不会?

看下面的图片:(假设是圆\(O_2\)覆盖圆\(O_1\))

(看不清楚图片请点击一下放大来看)求出\(a,b\)之后,就很容易利用向量求出两个交点坐标了.(具体怎么求就不要问我了吧QoQ)

然后我们确定这两个点关于点\(O_1\)的极角序,但是究竟是由哪一个指向哪一个呢?

我们只要再确定点\(O_2\)关于圆心\(O_1\)的极角序,并保证上述的区间经过这个位置即可.

具体的细节就只能自己体会了.可以参照我的代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
inline f2 sqr(const f2&x){
    return x*x; 
}
static const f2 PI=acos(-1.0);
 
#define N 1010
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
};
f2 dist(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
 
typedef Point vector;
inline vector Getvertical(vector _v){return vector(-_v.y,_v.x);}
inline f2 Getlength(vector _v){return sqrt(sqr(_v.x)+sqr(_v.y));}
inline vector Getunitvector(vector _v){
    f2 length=Getlength(_v);
    return vector(_v.x/length,_v.y/length);
}
 
struct Circle{
    Point o;f2 r;
    Circle(){}
    Circle(Point _o,f2 _r):o(_o),r(_r){}
    f2 get(const Point&B)const{return atan2(B.y-o.y,B.x-o.x);}
}C[N];
inline bool IsIntersect(const Circle&A,const Circle&B){
    return A.r+B.r>dist(A.o,B.o);
}
inline bool IsCover(const Circle&A,const Circle&B){
    return A.r>=B.r&&dist(A.o,B.o)<=A.r-B.r;
}
 
struct Interval{
    f2 l,r;
    Interval(){}
    Interval(f2 _l,f2 _r):l(_l),r(_r){}
    bool operator<(const Interval&B)const{return l<B.l;}
}S[N<<1];int id;
inline bool find(f2 l,f2 r,f2 x){
	if(l<=r)return x>=l&&x<=r;else return x>=l||x<=r;
}
inline void add(f2 l,f2 r){
    if(l<=r)S[++id]=Interval(l,r);else S[++id]=Interval(l,PI),S[++id]=Interval(-PI,r);
}
 
int main(){
    int n;scanf("%d",&n);
    register int i,j,k;
    for(i=1;i<=n;++i){
        scanf("%lf%lf%lf",&C[i].r,&C[i].o.x,&C[i].o.y);
    }
    f2 totans=0,a,b,d,ang1,ang2,ango;Point p1,p2; 
    vector v,_v;
    for(i=n;i>=1;--i){
        bool cover=0;id=0;
        for(j=i+1;j<=n&&!cover;++j)if(IsCover(C[j],C[i]))cover=1;
        if(!cover){
            for(j=i+1;j<=n;++j)if(IsIntersect(C[i],C[j])&&!IsCover(C[i],C[j])){
                d=dist(C[i].o,C[j].o);
                b=(sqr(C[i].r)-sqr(C[j].r)+sqr(d))/(2*d);
                a=sqrt(sqr(C[i].r)-sqr(b));
                v=C[i].o-C[j].o,_v=Getunitvector(Getvertical(v));
                p1=C[i].o+v*(b/d)+_v*a,p2=C[i].o+v*(b/d)+_v*(-a);
                ang1=C[i].get(p1),ang2=C[i].get(p2),ango=C[i].get(C[j].o);
                if(find(ang1,ang2,ango))add(ang1,ang2);else add(ang2,ang1);
            }
            totans+=2*PI*C[i].r;
            if(id){
                sort(S+1,S+id+1);
                f2 Maxr;
                for(j=1;j<=id;){
                    for(Maxr=S[j].r,k=j+1;k<=id;++k){
                        if(S[k].l>Maxr)break;
                        if(S[k].r>Maxr)Maxr=S[k].r;
                    }
                    totans-=C[i].r*(Maxr-S[j].l);
                    j=k;
                }
            }
        }
    }
    printf("%.3lf",totans);
    return 0;
}

BZOJ3357:[Usaco2004]等差数列 dp

思路:

我们令\(f[i][j]\)表示等差数列最后两项的下标分别为\(i,j\)时的最长长度.

显然我们有:

\[f[i][j]=max_{k=1}^{i-1}\{f[k][i]+1\}(2a[i]=a[j]+a[k])\]

重要的就是如何快速找出\(k\)的位置.

我们呢就可以将权值离散化,记录一下每个权值在序列中出现的位置.

于是我们要找的\(k\),显然就是权值相同时标号小于\(i\)且最大的一个.

因此我们维护一个vector然后二分就好了.

(注意\(n=1\)233)

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
 
#define N 2010
vector<int>v[N];
 
int a[N],b[N],id;
map<int,int>M;
 
int f[N][N];
 
int main(){
    int n;scanf("%d",&n);if(n==1){puts("1");return 0;}register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);for(b[0]=-1<<30,i=1;i<=n;++i)if(b[i]!=b[i-1])M[b[i]]=++id;
    for(i=1;i<=n;++i)v[M[a[i]]].push_back(i);
    int nowv,ins,siz;
    for(j=2;j<=n;++j){
        for(i=1;i<j;++i){
            f[i][j]=2;
            nowv=M[2*a[i]-a[j]];
            if(nowv){
                siz=v[nowv].size();
                if(v[nowv][0]<i){
                    int L=0,R=siz-1,mid;
                    while(L<R){
                        mid=(L+R+1)>>1;
                        if(v[nowv][mid]<i)L=mid;else R=mid-1;
                    }f[i][j]=max(f[i][j],f[v[nowv][L]][i]+1);
                }
            }
        }
    }
    int res=0;for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)res=max(res,f[i][j]);
    printf("%d",res);
    return 0;
}

BZOJ1345:[Baltic2007]序列问题Sequence 乱搞

思路:

首先我们考虑序列中最大的元素,如果它是当前区间的头或者尾,当然是只合并一次最优了,否则当然是至少要合并两次了.

将这个元素的影响去掉,然后将区间分裂开,递归处理就行了.容易发现总处理区间数是\(O(n)\)的.

那么现在我们的问题是,给出\(O(n)\)个询问,每次询问一段区间的最大值的标号.

那么我们有两种策略:

[1]RMQ ST算法 \(O(nlogn)-O(1) 空间O(nlogn)\)

[2]直接线段树 \(O(n)-O(logn) 空间O(n)\)

事实上[2]的常数很小,而[1]会TLE!再兼具空间,可以说,在这种询问次数下,[2]完爆[1]!

所以这样就水过去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
 
#define N 1000010
int a[N];
 
struct SegmentTree{
    int ins[262144*8],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        for(int i=1;i<=_siz;++i)ins[M+i]=i;
        a[0]=-INF;for(int i=M-1;i>=1;--i)ins[i]=a[ins[i<<1]]>a[ins[i<<1^1]]?ins[i<<1]:ins[i<<1^1];
    }
    inline int ask(int tl,int tr){
        int res=0;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if((~tl&1)&&(a[res]<a[ins[tl^1]]))res=ins[tl^1];
            if((tr&1)&&(a[res]<a[ins[tr^1]]))res=ins[tr^1];
        }return res;
    }
}Seg;
 
struct Intv{
    int l,r;Intv(){}Intv(int _l,int _r):l(_l),r(_r){}
}q[N];int fr,ta;
 
int main(){
    int n;Fio::Get(n);register int i,j;for(i=1;i<=n;++i)Fio::Get(a[i]);Seg.Init(n);
    long long ans=0;
    q[ta++]=Intv(1,n);Intv tmp;int ins;
    while(fr^ta){
        tmp=q[fr++];if(tmp.l==tmp.r)continue;ins=Seg.ask(tmp.l,tmp.r);
        if(ins==tmp.l)ans+=a[ins],q[ta++]=Intv(tmp.l+1,tmp.r);else if(ins==tmp.r)ans+=a[ins],q[ta++]=Intv(tmp.l,tmp.r-1);
        else ans+=2LL*a[ins],q[ta++]=Intv(tmp.l,ins-1),q[ta++]=Intv(ins+1,tmp.r);
    }
    printf("%lld\n",ans);
    return 0;
}

BZOJ1857:[Scoi2010]传送带 三分

思路:

显然一条比较优的路径是从\(A\)走到\(AB\)上一点\(X\),然后从\(X\)走到\(CD\)上一点\(Y\),然后从\(Y\)走到\(D\).

关键是\(X,Y\)如何确定.

我们能够发现\(X\)点确定时,随着\(Y\)的移动,总路程是一个单峰函数.

更加神奇的是,随着\(X\)的移动,通过我们上述三分得到的总路程也是一个单峰函数!

没什么说的,三分套三分就行了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define eps 1e-8
struct Point{
    f2 x,y;
    void read(){scanf("%lf%lf",&x,&y);}
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
}A,B,C,D;
 
int vab,vcd,vplane;
 
f2 sqr(const f2&x){return x*x;}
f2 Dist(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
f2 f(Point x,Point l,Point v,f2 k){
    return Dist(x,l+v*k)/vplane+Dist(l+v*k,l+v)/vcd;
}
f2 Solve(Point x,Point l,Point r){
    Point v=l-r;
    f2 L=0,R=1,LL,RR,ansl,ansr,lastans=1e12,nowans;
    while(1){
        LL=L+(R-L)/3,RR=R-(R-L)/3;
        ansl=f(x,l,v,LL),ansr=f(x,l,v,RR);
        if(ansl<ansr)R=RR,nowans=ansl;else L=LL,nowans=ansr;
        if(fabs(nowans-lastans)<1e-5)break;lastans=nowans;
    }
    return lastans;
}
 
int main(){
    A.read(),B.read(),C.read(),D.read();
    scanf("%d%d%d",&vab,&vcd,&vplane);
    f2 L=0,R=1,LL,RR,ansl,ansr,lastans=1e12,nowans;Point v=A-B;
    while(1){
        LL=L+(R-L)/3,RR=R-(R-L)/3;
        ansl=Dist(A,A+v*LL)/vab+Solve(A+v*LL,C,D),ansr=Dist(A,A+v*RR)/vab+Solve(A+v*RR,C,D);
        if(ansl<ansr)R=RR,nowans=ansl;else L=LL,nowans=ansr;
        if(fabs(nowans-lastans)<1e-5)break;lastans=nowans;
    }
    printf("%.2lf",lastans);
    return 0;
}

BZOJ1811:[Ioi2005]mea 乱搞

思路:发现若\(S_1\)不同,则整个序列就不同.因此我们的任务就是找出有多少种\(S_1\)的方案.

我们把\(S_2...S_{n+1}\)都用关于\(S_1\)的一次函数表示,则我们有\(n\)个线性约束条件,对于第\(i\)个条件,我们有\(S_{i}\leq{S_{i+1}}\).

直接接出\(S_1\)的上下界即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 5000010
int k[N];LL b[N];
 
int main(){
    int n;scanf("%d",&n);register int i;LL a;
    k[1]=1,b[1]=0;
    for(i=2;i<=n+1;++i)scanf("%lld",&a),k[i]=-k[i-1],b[i]=2LL*a-b[i-1];
    LL up=1LL<<60,down=-1LL<<60;
    for(i=1;i<=n;++i){
        if(k[i]==1)up=min(up,b[i+1]-b[i]);
        else down=max(down,b[i]-b[i+1]);
    }
    if(up>0)up/=2;else{if(up&1)up=(up-1)/2;else up/=2;}
    if(down>0){if(down&1)down=(down+1)/2;else down/=2;}else down/=2;
    if(up<down){puts("0");return 0;}else printf("%lld",up-down+1);
    return 0;
}

BZOJ2600:[Ioi2011]ricehub 贪心+二分

思路:

显然当我们选定一个米仓的位置后,选择的粮田的位置是一段连续区间.

我们不妨枚举枚举所有的粮田区间,于是我们发现在给定粮田区间时,最优的米仓位置必定是中位数,可以\(O(1)\)确定.

若我们枚举所有的区间,则是\(O(R^2)\)的.

于是我们考虑固定区间起点,则需要的花费显然随区间终点右移而单调不减.于是我们二分得到最优的区间终点即可.

时间复杂度\(O(nlogn)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 100010
int a[N];
LL sum[N];
 
long long getsum(int l,int r){return sum[r]-sum[l-1];}
long long getinterval(int l,int r){
    if(l==r)return 0;
    if((r-l+1)&1){
        int midins=(l+r)>>1;
        return getsum(midins+1,r)-getsum(l,midins-1);
    }
    else{
        int midins=(l+r)>>1;
        return getsum(midins+1,r)-getsum(l,midins);
    }
}
 
int main(){
    int R,L;LL B;scanf("%d%d%lld",&R,&L,&B);
    register int i,j;for(i=1;i<=R;++i)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
     
    int l,r,mid,res=0;
    for(i=1;i<=R;++i){
        l=i,r=R;while(l<r){mid=(l+r+1)>>1;if(getinterval(i,mid)<=B)l=mid;else r=mid-1;}res=max(res,l-i+1);
    }
     
    printf("%d",res);
     
    return 0;
}

3544:[ONTAK2010]Creative Accounting 贪心+迷の卡常数

思路:

维护一下前缀和对\(M\)取模得到的值.

考虑当一段区间的结尾固定时,如何寻找区间的起始端点才能使得答案最优.

首先是减去一个比当前小的数,为了使答案最大,当然是减去0,也就是用当前的模来更新答案;

其次是减去一个比当前大的数,这个需要加上\(M\),由于贪心的使答案最大,我们就减去一个之前出现过的比当前大的最小的模来更新答案.这东西用一个set维护就行.

然后我被迷の卡常数了QoQ.

这样写:upper_bound(s.begin(),s.end(),sum[i])就TLE.(T的不是一点半点)

这样写:s.upper_bound(sum[i])就AC.

这TM是什么鬼?

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Getunsign(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sign)x=-x;
    }
}
 
#define N 200010
LL a[N],sum[N],p;
set<LL>s;
 
int main(){
    //freopen("tt.in","r",stdin);
    using namespace Fio;
    int n;Getunsign(n);Getunsign(p);
    register int i,j;for(i=1;i<=n;++i){Get(a[i]),a[i]%=p;if(a[i]<0)a[i]+=p;}
    for(i=1;i<=n;++i){sum[i]=sum[i-1],sum[i]+=a[i];if(sum[i]>=p)sum[i]-=p;}
     
    LL nowans=-1;
    for(i=1;i<=n;++i){
        if(sum[i]>nowans)nowans=sum[i];
        set<LL>::iterator it=s.upper_bound(sum[i]);
        if(it!=s.end()&&nowans<sum[i]-*it+p)nowans=sum[i]-*it+p;
        s.insert(sum[i]);
    }
     
    printf("%lld",nowans);
     
    return 0;
}

BZOJ3866:The Romantic Hero dp

思路:

令\(f[i][j]\)表示最后一个数的位置\(\leq{i}\),异或起来等于\(j\)的序列数,\(g[i][j]\)表示第一个数的位置\(\geq{i}\),与起来等于\(j\)序列数.

我们差分之后就很容易得到结尾、开头位置确定的异或、与的序列个数了.

这两个东西知道之后,随便维护个前缀和什么的就行了.

(大常数\(O(n^2)\),目前倒数第一)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define N 1010
#define M 1024
int f[N][M],g[N][M],a[N],add[M][N];
  
static const int mod=(1e9)+7;
  
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
inline int dec(int x,int y){return (x-y+mod)%mod;}
int main(){
    int T;scanf("%d",&T);
    register int i,j;int n;
    while(T--){
        scanf("%d",&n);for(i=1;i<=n;++i)scanf("%d",&a[i]);
        for(memset(f,0,sizeof f),i=1;i<=n;++i){
            inc(f[i][a[i]],1);
            for(j=0;j<M;++j)inc(f[i][a[i]^j],f[i-1][j]);
            for(j=0;j<M;++j)inc(f[i][j],f[i-1][j]);
        }
        for(memset(g,0,sizeof g),i=n;i>=1;--i){
            inc(g[i][a[i]],1);
            for(j=0;j<M;++j)inc(g[i][a[i]&j],g[i+1][j]);
            for(j=0;j<M;++j)inc(g[i][j],g[i+1][j]);
        }
          
        for(i=n;i>=1;--i)for(j=0;j<M;++j)f[i][j]=dec(f[i][j],f[i-1][j]);
        for(i=1;i<=n;++i)for(j=0;j<M;++j)g[i][j]=dec(g[i][j],g[i+1][j]);
          
        for(j=0;j<M;++j)for(i=n;i>=1;--i)add[j][i]=add[j][i+1],inc(add[j][i],g[i][j]);
          
        int ans=0;
        for(j=0;j<M;++j)for(i=1;i<=n;++i)inc(ans,(long long)f[i][j]*add[j][i+1]%mod);
          
        printf("%d\n",ans);
    }
      
    return 0;
}

BZOJ3277:串 后缀自动机+离线处理+树状数组(&&BZOJ3473)

思路:

水题一道.

首先建立广义后缀树.

然后利用离线+树状数组搞出每一个节点在多少个串中.

然后如果这个节点在不少于\(k\)个串中,我们令这个结点的权值为这个节点父亲边的字符个数,否则为0.

随后我们预处理一下从根到每个节点路径上的权值和.

于是每个字符串的答案等于所有这个字符串的后缀节点的从根到该节点的权值和.

时间复杂度\(O(nlogn)\).

(貌似比一些后缀数组的神方法要好多了QoQ)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
 
int tranc[N<<1][26],len[N<<1],pa[N<<1],cnt,root,last;
inline int newnode(int l){len[++cnt]=l;return cnt;}
 
struct Graph{
    int head[N<<1],next[N<<1],end[N<<1],ind;
    inline void addedge(int a,int b){int q=++ind;end[q]=b,next[q]=head[a],head[a]=q;}
}w,g,sav;
 
char s[N];
 
int seq[N<<1],in[N<<1],out[N<<1],tclock;
inline void dfs(int x){
    in[x]=++tclock,seq[tclock]=x;
    for(int j=g.head[x];j;j=g.next[j])dfs(g.end[j]);
    out[x]=tclock;
}
 
struct Ask{
    int lab,l,r;
    Ask(){}
    Ask(int _lab,int _l,int _r):lab(_lab),l(_l),r(_r){}
    bool operator<(const Ask&B)const{return r<B.r;}
}S[N<<1];
 
int ans[N<<1],lastins[N];
 
int A[N<<1];
inline void mdf(int x,int add){
    for(;x<=cnt;x+=x&-x)A[x]+=add;
}
inline int ask(int x){
    int r=0;for(;x;x-=x&-x)r+=A[x];return r;
}
 
int v[N<<1];
 
void dfs2(int x){
    v[x]+=v[pa[x]];
    for(int j=g.head[x];j;j=g.next[j])dfs2(g.end[j]);
}
 
void get(int x){
    for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");
}
 
int main(){
    int n,lim;scanf("%d%d",&n,&lim);
     
    register int i,j,k;int y;int p,np,q,nq,rep,tmp;
    for(root=newnode(0),i=1;i<=n;++i){
        scanf("%s",s);int l=strlen(s);
        for(last=root,j=l-1;j>=0;--j){
            if((p=tranc[last][y=s[j]-'a'])!=0){
                if(len[p]==len[last]+1)last=p;
                else{
                    rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
                    memcpy(tranc[rep],tranc[p],sizeof tranc[p]);
                    for(tmp=last;tmp&&tranc[tmp][y]==p;tmp=pa[tmp])tranc[tmp][y]=rep;
                    last=rep;
                }
            }
            else{
                np=newnode(len[last]+1);
                for(p=last;p&&!tranc[p][y];p=pa[p])tranc[p][y]=np;
                if(!p)pa[np]=root;
                else{
                    q=tranc[p][y];
                    if(len[q]==len[p]+1)pa[np]=q;
                    else{
                        nq=newnode(len[p]+1),pa[nq]=pa[q],pa[np]=pa[q]=nq;
                        memcpy(tranc[nq],tranc[q],sizeof tranc[q]);
                        for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
                    }
                }last=np;
            }
            w.addedge(last,i);
            sav.addedge(i,last);
        }
    }
     
    for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
    dfs(1);
     
    for(i=1;i<=cnt;++i)S[i]=Ask(i,in[i],out[i]);sort(S+1,S+cnt+1);
    for(k=i=1;i<=cnt;++i){
        for(j=w.head[seq[i]];j;j=w.next[j]){
            if(lastins[w.end[j]])mdf(lastins[w.end[j]],-1);mdf(lastins[w.end[j]]=i,1);
        }
        for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
    }
     
    for(i=1;i<=cnt;++i)v[i]=ans[i]>=lim?len[i]-len[pa[i]]:0;
     
    dfs2(1);
     
    long long nowans;
    for(i=1;i<=n;++i){
        if(i>1)putchar(' ');
        for(nowans=0,j=sav.head[i];j;j=sav.next[j])nowans+=v[sav.end[j]];
        printf("%lld",nowans);
    }
     
    return 0;
}