UVA-11625-Nice Prefixes (DP+矩阵快速幂)

题面

题意:

　　你有K个字母，你需要用K个字母组成L长度的字符串，定义对于该字符串的任意前缀P 必须满足 $\mathit{max\{count(\ P_k\ _{\(k= K_{1,2,3,4,...}) \ } )\}}-\mathit{min\{count(\ P_k\ _{\(k= K_{1,2,3,4,...}) \ } )\}}\leq 2$ ，输出方案数%1000000007的值。

思路:

　　首先可以想到一种简单的dp方程 dp [ len ] [ a ] [b ] 表示当前字符串长度为len 个数为最多的字母有 a个个数次多的有b个 (那么个数最少的有k-a-b个)状态数有 100*100，没办法矩阵快速幂加速dp.

　　考虑对于某个固定长度 len 如果确定 a，容易发现 b = (len % K - a)，发现dp方程可以转化成 dp[ len ] [ a ] 但是依旧不能矩阵快速幂，因为对于len-1到len的每个状态 a 的转移方程的系数与 len%K 相关，

于是稍微转换一下方程由 len-K 转移到 len (每次放K个字符 ),这时候容易发现转移方程的系数也不在改变了于是我们先预处理放K步的dp方程的系数矩阵然后转移L/K次（利用矩阵快速幂加速)，最后剩下L%K步暴力dp就好了

(参考了别人的题解)

代码:

#include <stdio.h>

#include <bits/stdc++.h>

#define IV inline void

typedef unsigned long long ull;

using namespace std;

const int mod = 1e9+;

ull dp[][][],B[][],A[][],C[][];

int K,t;

IV DP(int L)

{

    for (int len=;len<=L;len++){

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

            for (int j=;j<=K;j++){

                int w=*K+len-;

                int l2=w-*(j-);

                while (l2+(j-)>K)l2-=K;

                if (l2>=)dp[len][i][j%K]+=dp[len-][i][j-]*(l2);

                if (j==&&l2>=)dp[len][i][j%K]+=dp[len-][i][l2]*(l2);

                l2=w-*j;

                while (l2+j>K)l2-=K;

                int l3=K-j-l2;

                if (l2>=&&l3>=)dp[len][i][j%K]+=dp[len-][i][j%K]*(l3);

                dp[len][i][j%K]%=mod;

            }

        }

    }

}

IV init()

{

    memset(dp,,sizeof(dp));

    memset(B,,sizeof(B));

    B[][]=;

    for (int i=;i<K;i++)dp[][i][i]=;

    DP(K);

    for (int i=;i<K;i++)for (int j=;j<K;j++)A[i][j]=dp[K][i][j];

}

IV mul(ull A[][],ull B[][])

{

    memset(C,,sizeof(C));

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

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

            for (int k=;k<K;k++)

                C[i][k]=(C[i][k]+A[i][j]*B[j][k])%mod;

    memcpy(A,C,sizeof(C));

}

IV pow(long long n)

{

    while (n){

        if (n&)mul(B,A);

        mul(A,A);

        n>>=;

    }

}

int main()

{

    long long n,ans;

    scanf("%d",&t);

    while (t--&&~scanf("%lld%d",&n,&K)){

        ans=;

        init();

        pow(n/K);

        memset(dp,,sizeof(dp));

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

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

                dp[][i][j]=B[i][j];

        DP(n%K);

        int L=n%K;

        for (int j=;j<K;j++)ans+=dp[L][][j];

        printf("%lld\n",ans%mod);

    }

    return ;

}

巴特西

UVA-11625-Nice Prefixes (DP+矩阵快速幂)

最新文章

热门文章