题解:

(我这个大傻叉连这题都不会做了)

首先肯定是转移了...

我们单独考虑每个球,变化的概率都是$\frac{1}{m}$.

于是令$f_i$表示编号为$i$的球的个数,考虑一次操作$f_i$的变化.

考虑单个标号为$i$的球对$f_i$的影响:$\frac{1}{m}\times{0}+(1-\frac{1}{m})\times{1}$

考虑单个标号为$i-1$的球对$f_i$的影响:$\frac{1}{m}\times{1}+(1-\frac{1}{m})\times{0}$

然后我们就搞出了转移矩阵.

有意思的是,这是一个循环矩阵!

也就是说,从第二行开始,每一行都是上一行右移一位得到的.

显而易见,循环矩阵的乘积依然是循环矩阵.

所以我们只要暴力算出第一行就行了,所以可以$O(n^2)$暴力,也可以利用FFT优化至$O(nlogn)$.

这样的话就能做这道题目了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 1010
int n,m,k,a[N];
struct Vector{
    f2 line[N],row[N];
    inline void operator*=(const Vector&B){
        static f2 _line[N];
        int i,j,k;
        for(i=0;i<n;++i)
            _line[i]=0;
        for(i=0;i<n;++i)
            for(j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
                _line[i]+=line[k]*B.row[j];
        for(i=0;i<n;++i)
            line[i]=_line[i];
        for(i=0;i<n;++i)
            row[(n-i)%n]=line[i];
    }
}t,re;
int main(){
    cin>>n>>m>>k;
    int i,j;
    for(i=0;i<n;++i)
        scanf("%d",&a[i]);
    re.line[0]=re.row[0]=1;
    t.line[0]=(f2)(m-1)/m;
    t.line[1]=1.0/m;
    t.row[0]=(f2)(m-1)/m;
    t.row[n-1]=1.0/m;
    for(;k;k>>=1,t*=t)
        if(k&1)
            re*=t;
     
    f2 ans;
    for(i=0;i<n;++i){
        for(ans=0,j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
            ans+=a[k]*re.row[j];
        printf("%.3lf\n",ans);
    }
    return 0;
}

思路:

从前向后考虑每一个点,不难发现每个点只能向它的前\(k\)个点连边.

因此我们维护一下最后\(k\)个点的连通性,然后做状压dp.

我们用最小表示法来表示\(k\)个点的连通性,比如12123这种形式,相同的数字表示在相同集合中.

然后我们就枚举一下第\(k+1\)个点如何向前\(k\)个点连边.

注意:合法的连边不能出现环,同时还要保证第\(1\)个点不能被孤立.

然后就有了一个转移矩阵,就可以跑矩乘了.

注意每个状态的初始方案并不是一,而是每个每个连通图的所有生成树的方案之积.

而由Prufer序列可得\(n\)个点的生成树总数为\(n^{n-2}\).

至此应该没有什么问题了(除了代码实现).

#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
long long n;int k;
 
int lim;
 
int cnt,seq[110][10],now[10],vis[10];
 
void dfs(int dep){
    if(dep==k+1){
        memset(vis,0,sizeof vis);
        for(int i=1;i<=k;++i)if(!vis[now[i]])vis[now[i]]=i;
        for(int i=1;i<=lim;++i)if(!vis[i])return;
        for(int i=1;i<=lim;++i)for(int j=i+1;j<=lim;++j)if(vis[i]>vis[j])return;
         
        ++cnt;for(int i=1;i<=k;++i)seq[cnt][i]=now[i];
        return;
    }
     
    for(int i=1;i<=lim;++i)now[dep]=i,dfs(dep+1);
}
 
#define Min(x,y) ((x)<(y)?(x):(x))
 
inline int calc(int d){
    int mi=1,re=0;
    for(int i=1;i<=k;++i)re+=mi*seq[d][i],mi*=10;
    return re;
}
map<int,int>M;
 
static const int mod=65521;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
 
struct Matrix{
    int w,h,d[110][110];
    Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
     
    inline void operator*=(const Matrix&B){
        Matrix C(w,B.h);
        for(int i=1;i<=C.w;++i)for(int j=1;j<=C.h;++j)
            for(int k=1;k<=h;++k)inc(C.d[i][j],(long long)d[i][k]*B.d[k][j]%mod);
        *this=C;
    }
};
 
int pre[10],pa[10],nowseq[10];
 
inline int find(int p[],int x){return x==p[x]?x:p[x]=find(p,p[x]);}
inline void merge(int p[],int x,int y){p[find(p,x)]=find(p,y);}
 
const int get[]={1,1,1,3,16,125};
 
int main(){
    scanf("%d%lld",&k,&n),k=Min(k,n-1);register int i,j;
     
    for(i=1;i<=k;++i){
        lim=i,dfs(1);
    }
     
    Matrix ans(1,cnt);
    for(i=1;i<=cnt;++i){
        ans.d[1][i]=1;
        for(j=1;j<=k;++j){int count=0;for(int q=1;q<=k;++q)if(seq[i][q]==j)++count;ans.d[1][i]*=get[count];}
         
        M[calc(i)]=i;
    }
     
    Matrix add(cnt,cnt);
     
    for(int t=1;t<=cnt;++t){
        for(i=1;i<=k+1;++i)pre[i]=i;
        for(i=1;i<=k;++i)for(j=i+1;j<=k;++j)if(seq[t][i]==seq[t][j])merge(pre,i,j);
         
        for(int S=0;S<(1<<k);++S){
            memcpy(pa,pre,sizeof pa);
            bool can=1;
            for(i=0;i<k;++i)if((S>>i)&1){if(find(pa,i+1)==find(pa,k+1))can=0;else merge(pa,i+1,k+1);}
            if(!can)continue;
             
            for(i=1;i<=k+1;++i)pa[i]=find(pa,i);
             
            memset(nowseq,0,sizeof nowseq);
            int id=0;
            for(i=1;i<=k+1;++i){
                if(nowseq[i]==0){
                    ++id;
                    for(j=i;j<=k+1;++j)if(pa[j]==pa[i])nowseq[j]=id;
                }
            }
             
            bool ok=0;
            for(i=2;i<=k+1;++i)if(nowseq[1]==nowseq[i]){ok=1;break;}
             
            if(ok){
                memset(nowseq,0,sizeof nowseq);
                id=0;
                for(i=2;i<=k+1;++i){
                    if(nowseq[i]==0){
                        ++id;
                        for(j=i;j<=k+1;++j)if(pa[j]==pa[i])nowseq[j]=id;
                    }
                }
                 
                int mi=1,re=0;
                for(i=2;i<=k+1;++i)re+=mi*nowseq[i],mi*=10;
                 
                if(M[re]==0)puts("WA");
                inc(add.d[t][M[re]],1);
            }
        }
    }
     
    n-=k;
    for(;n;n>>=1,add*=add)if(n&1)ans*=add;
     
    printf("%d",ans.d[1][1]);
     
    return 0;
}

思路:

首先考虑如果一个串固定时,如何求出最多的出现次数.

当模式串存在覆盖关系时,很显然可以舍弃掉一些.那么现在所有的串之间都不存在覆盖关系.

那么我们可以从前向后扫描,如果出现一个完整的模式串,答案加1,同时将指针移到下一个位置继续刚才的操作.

由于不存在覆盖关系,这样的贪心是很显然的,不信的话可以自己画图看看.

考虑将模式串建成AC自动机.令\(P[i][j]\)表示串长为\(i\),现在处于AC自动机上的节点\(j\)上的概率.这个很容易用矩阵乘法搞定.

那么我们的答案是是什么呢?

考虑从某个节点转移到某个完全包含某个模式串的节点,那么此时答案+1,同时状态回到根节点.我们只要在矩阵中加一维计数器来搞就行了.

其实没说什么= =  不懂自己看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int ch[80][26],fail[80],end[80],cnt,q[80],fr,ta;
 
char s[20],sav[6][20];int len[6];bool covered[6];
 
typedef long double f4;
 
struct Matrix{
    f4 d[81][81];int w,h;
    Matrix(){}
    Matrix(int _w,int _h):w(_w),h(_h){}
     
    void operator*=(const Matrix&B){
        register int i,j,k;
        Matrix res(w,B.h);
        for(i=0;i<res.w;++i)for(j=0;j<res.h;++j){
            res.d[i][j]=0;for(k=0;k<h;++k)res.d[i][j]+=d[i][k]*B.d[k][j];
        }
        *this=res;
    }
};
 
bool cover(int a,int b){
    if(len[a]<len[b])return 0;
    register int i,j;
    for(i=1;i+len[b]-1<=len[a];++i){
        bool ok=1;
        for(j=1;j<=len[b];++j)if(sav[a][i+j-1]!=sav[b][j])ok=0;
        if(ok)return 1;
    }
    return 0;
}
 
int main(){
    int n,L,k;scanf("%d%d%d",&n,&L,&k);register int i,j;
     
    for(i=1;i<=n;++i)scanf("%s",sav[i]+1),len[i]=strlen(sav[i]+1);
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(cover(i,j))covered[i]=1;
     
    bool allcovered=1;for(i=1;i<=n;++i)if(!covered[i])allcovered=0;
    if(allcovered)covered[1]=0;
     
    int p,y;
    for(i=1;i<=n;++i)if(!covered[i]){
        p=0;for(j=1;j<=len[i];++j){if(!ch[p][y=sav[i][j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
        end[p]=1;
    }
     
    for(j=0;j<k;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<k;++j){
            if((v=ch[u][j])){
                q[ta++]=v;
                for(r=fail[u];r&&!ch[r][j];r=fail[r]);
                end[v]|=end[fail[v]=ch[r][j]];
            }else ch[u][j]=ch[fail[u]][j];
        }
    }
     
    Matrix res(1,cnt+2);res.d[0][0]=1;
     
    Matrix add(cnt+2,cnt+2);add.d[cnt+1][cnt+1]=1;
    for(i=0;i<=cnt;++i){
        for(j=0;j<k;++j){
            if(end[ch[i][j]])add.d[i][cnt+1]+=(f4)1/k,add.d[i][0]+=(f4)1/k;
            else add.d[i][ch[i][j]]+=(f4)1/k;
        }
    }
     
    for(;L;L>>=1,add*=add)if(L&1)res*=add;
     
    double output=res.d[0][cnt+1];
    printf("%.6lf",output);
     
     
    return 0;
}

思路:

我们可以预处理出一个矩阵\(P\),其中\(P[i][j]\)表示从\(i\)到\(j\)的道路数目.

这样我们大概可以搞出从\(u\)到\(v\)正好是\(d\)条路径的方案数.如果是不大于\(d\)条路径,我们就可以加一个计数器,每次累加能够到\(v\)的方案数.

这样就是一个\((N+1)*(N+1)\)的转移矩阵.如果我们每次用这个转移矩阵乘的话就要爆掉了.

发现矩阵\(P\)的算法非常奇葩.我们可以将其分解成一个\((N+1)*(K+1)\)的矩阵\(out\)与一个\((K+1)*(N+1)\)的矩阵\(in\)的乘积.

于是\(P^d=(out*in)^d\).

我们发现\(P^d=(out*in)^d=out*(in*out)^{d-1}*in\).注意到\(in*out\)是一个\((K+1)*(K+1)\)的矩阵,算起来毫无压力.

我们的答案矩阵是一个\(1*(N+1)\)的矩阵,容易发现这些东西乘到一起也只是\(O(NK^2)\)级别的.

因此我们的复杂度就是\(O(Q(K^3logd+NK^2))\).

(注意本题卡常数)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
static const int mod=(1e9)+7;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
struct Matrix{
    int d[1010][1010],w,h;
    Matrix(){}
    Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
    void output(){
        printf("w=%d h=%d\n",w,h);
        for(int i=1;i<=w;++i){
            for(int j=1;j<=h;++j)printf("%d ",d[i][j]);puts("");
        }
        puts("");
    }
};
long long calc=0;
Matrix t,res,ret;
Matrix mul(const Matrix&A,const Matrix&B){
    res.w=A.w,res.h=B.h;
    for(int i=1;i<=res.w;++i)for(int j=1;j<=res.h;++j){
        res.d[i][j]=0;for(int k=1;k<=A.h;++k)++calc,inc(res.d[i][j],(long long)A.d[i][k]*B.d[k][j]%mod);
    }
    return res;
}
Matrix Pow(const Matrix&x,int y){//for w=h
    t=ret=x;y--;for(;y;y>>=1,t=mul(t,t))if(y&1)ret=mul(ret,t);return ret;
}
#define N 1010
#define M 21
int n,m,in[N][M],out[N][M];
Matrix Solve1,Solve2,Solve3,ans;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;
    for(i=1;i<=n;++i){for(j=1;j<=m;++j)scanf("%d",&out[i][j]);for(j=1;j<=m;++j)scanf("%d",&in[i][j]);}
    int q,u,v,d;
    scanf("%d",&q);
    while(q--){
        calc=0;//debug
        scanf("%d%d%d",&u,&v,&d);
        if(d==0)printf("%d\n",u==v?1:0);
        else if(d==1){
            int ret=0;for(int i=1;i<=m;++i)ret=(ret+(long long)out[u][i]*in[v][i]%mod)%mod;
            printf("%d\n",(ret+(u==v?1:0))%mod);
        }
        else{
            Solve1=Matrix(n+1,m+1),Solve2=Matrix(m+1,n+1);
            for(i=1;i<=n;++i)for(j=1;j<=m;++j)Solve1.d[i][j]=out[i][j];
            Solve1.d[n+1][m+1]=1;
            for(i=1;i<=n;++i)for(j=1;j<=m;++j)Solve2.d[j][i]=in[i][j];
            for(j=1;j<=m;++j)Solve2.d[j][n+1]=in[v][j];
            Solve2.d[m+1][n+1]=1;
            //Solve1.output();
            //Solve2.output();
            Solve3=mul(Solve2,Solve1);//Solve3.output();
            Solve3=Pow(Solve3,d-1);
            ans=Matrix(1,n+1);ans.d[1][u]=1;
            ans=mul(ans,Solve1),ans=mul(ans,Solve3),ans=mul(ans,Solve2);
            printf("%d\n",(ans.d[1][n+1]+(u==v?1:0))%mod);
        }
        //printf("%I64d\n",calc);
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
static const int mod=(1e9)+7;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
#define N 1010
#define M 22
int n,m,in[N][M],out[N][M];
int Solve1[N][M],Solve2[M][N],Solve3[M][M],ans[N][N],reg[N][N],t[M][M],one[M][M];
inline void work(int d){//solve Solve3^d
    register int i,j,k;
    memset(one,0,sizeof one);for(i=1;i<=m+1;++i)one[i][i]=1;
    for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j)t[i][j]=Solve3[i][j];
    while(d){
        if(d&1){
            for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j){
                reg[i][j]=0;for(k=1;k<=m+1;++k)inc(reg[i][j],(long long)one[i][k]*t[k][j]%mod);
            }
            for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j)one[i][j]=reg[i][j];
        }
        d>>=1;
        for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j){
            reg[i][j]=0;for(k=1;k<=m+1;++k)inc(reg[i][j],(long long)t[i][k]*t[k][j]%mod);
        }
        for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j)t[i][j]=reg[i][j];
    }
    for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j)Solve3[i][j]=one[i][j];
}
void pr1(){
    puts("Solve1");
    for(int i=1;i<=n+1;++i){
        for(int j=1;j<=m+1;++j)printf("%9d ",Solve1[i][j]);puts("");
    }
}
void pr2(){
    puts("Solve2");
    for(int i=1;i<=m+1;++i){
        for(int j=1;j<=n+1;++j)printf("%9d ",Solve2[i][j]);puts("");
    }
}
void pr3(){
    puts("Solve3");
    for(int i=1;i<=m+1;++i){
        for(int j=1;j<=m+1;++j)printf("%9d ",Solve3[i][j]);puts("");
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    scanf("%d%d",&n,&m);
    register int i,j,k;
    for(i=1;i<=n;++i){for(j=1;j<=m;++j)scanf("%d",&out[i][j]);for(j=1;j<=m;++j)scanf("%d",&in[i][j]);}
    int q,u,v,d;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&u,&v,&d);
        if(d==0)printf("%d\n",u==v?1:0);
        else if(d==1){
            int ret=0;for(int i=1;i<=m;++i)ret=(ret+(long long)out[u][i]*in[v][i]%mod)%mod;
            printf("%d\n",(ret+(u==v?1:0))%mod);
        }
        else{
            memset(Solve1,0,sizeof Solve1);
            for(i=1;i<=n;++i)for(j=1;j<=m;++j)Solve1[i][j]=out[i][j];
            Solve1[n+1][m+1]=1;
            memset(Solve2,0,sizeof Solve2);
            for(i=1;i<=n;++i)for(j=1;j<=m;++j)Solve2[j][i]=in[i][j];
            for(j=1;j<=m;++j)Solve2[j][n+1]=in[v][j];
            Solve2[m+1][n+1]=1;
            
            for(i=1;i<=m+1;++i)for(j=1;j<=m+1;++j){
                Solve3[i][j]=0;for(k=1;k<=n+1;++k)inc(Solve3[i][j],(long long)Solve2[i][k]*Solve1[k][j]%mod);
            }
            
            work(d-1);
            
            for(j=1;j<=n+1;++j)ans[1][j]=0;ans[1][u]=1;
            
            for(i=1;i<=1;++i)for(j=1;j<=m+1;++j){
                reg[i][j]=0;for(k=1;k<=n+1;++k)inc(reg[i][j],(long long)ans[i][k]*Solve1[k][j]%mod);
            }for(i=1;i<=1;++i)for(j=1;j<=m+1;++j)ans[i][j]=reg[i][j];
            
            for(i=1;i<=1;++i)for(j=1;j<=m+1;++j){
                reg[i][j]=0;for(k=1;k<=m+1;++k)inc(reg[i][j],(long long)ans[i][k]*Solve3[k][j]%mod);
            }for(i=1;i<=1;++i)for(j=1;j<=m+1;++j)ans[i][j]=reg[i][j];
            
            for(i=1;i<=1;++i)for(j=1;j<=n+1;++j){
                reg[i][j]=0;for(k=1;k<=m+1;++k)inc(reg[i][j],(long long)ans[i][k]*Solve2[k][j]%mod);
            }for(i=1;i<=1;++i)for(j=1;j<=n+1;++j)ans[i][j]=reg[i][j];
            
            printf("%d\n",(ans[1][n+1]+(u==v?1:0))%mod);
        }
    }
    return 0;
}

思路:

首先注意到不允许出现矩形,而这个条件很难限制,不过我们可以将矩形也一起算进去,在最后减掉,因为矩形的数目是可以\(O(1)\)计算的.

接下来就是考虑令\(f_i\)表示周长为\(i\)的合法方案数.

我们考虑几种情况:

[1]左侧有一个高度为1的方块

[2]右侧有一个高度为1的方块

[3]左右两侧均没有一个高度为1的方块

对于[1][2],我们可以分别在左侧和右侧拿走一个方块使得周长减少2,对于[3],我们可以拿走下面的一层使得周长减少2.不难发现这些关系都是一一对应的.

下面考虑一个问题,如果一种形态是两侧均有一个方块,那么我们事实上是算了两遍的.所以我们需要减去这种情况.而显然这种情况与周长减少了4的情况一一对应.

因此我们有:\(f_i=3f_{i-2}-f_{i-4}\)

利用矩阵乘法即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
static const int mod=987654321;
struct Matrix{
    int w,h;LL d[2][2];
    Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
    inline void operator*=(const Matrix&B){
        Matrix C(w,B.h);
        register int i,j,k;
        for(i=0;i<C.w;++i)
            for(j=0;j<C.h;++j)
                for(k=0;k<h;++k)
                    C.d[i][j]=(C.d[i][j]+d[i][k]*B.d[k][j])%mod;
        *this=C;
    }
};
 
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        if(n<=3||n&1){puts("0");continue;}
        int t=n/2-1,res;
        if(t==1)res=1;else if(t==2)res=2;
        else{
            Matrix ans(1,2);ans.d[0][0]=1,ans.d[0][1]=2;
            Matrix add(2,2);add.d[0][0]=0,add.d[0][1]=-1,add.d[1][0]=1,add.d[1][1]=3;
            Matrix one(2,2);one.d[0][0]=one.d[1][1]=1;
            t-=2;for(;t;t>>=1,add*=add)if(t&1)one*=add;
            ans*=one;
            res=ans.d[0][1];
        }
        res=((LL)res-(n/2-1)+mod)%mod;
        printf("%d\n",res);
    }return 0;
}