首页 > 代码库 > bnu 34985 Elegant String（矩阵快速幂+dp推导公式）

bnu 34985 Elegant String（矩阵快速幂+dp推导公式）

2024-07-17 23:12:38   217人阅读

Elegant String

Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld      Java class name: Main
Prev 
Submit Status Statistics Discuss
 Next
Type: 
None
     
    We define a kind of strings as elegant string: among all the substrings of an elegant string, none of them is a permutation of "0, 1,…, k".
    Let function(n, k) be the number of elegant strings of length n which only contains digits from 0 to k (inclusive). Please calculate function(n, k).
     

    Input

    Input starts with an integer T (T ≤ 400), denoting the number of test cases.
     
    Each case contains two integers, n and k. n (1 ≤ n ≤ 1018) represents the length of the strings, and k (1 ≤ k ≤ 9) represents the biggest digit in the string.
     

    Output

    For each case, first output the case number as "Case #x: ", and x is the case number. Then output function(n, k) mod 20140518 in this case. 
     

    Sample Input

    2
1 1
7 6

    Sample Output

    Case #1: 2
Case #2: 818503

    Source

    2014 ACM-ICPC Beijing Invitational Programming Contest

    题解及代码：



    #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const long long mod=20140518;

struct mat
{
    ll t[10][10];
    void set()
    {
        memset(t,0,sizeof(t));
    }
} a,b;

mat multiple(mat a,mat b,ll n,ll p)
{
    ll i,j,k;
    mat temp;
    temp.set();
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
        {
            if(a.t[i][j]!=0)
                for(k=0; k<n; k++)
                    temp.t[i][k]=(temp.t[i][k]+a.t[i][j]*b.t[j][k])%p;
        }
    return temp;
}

mat quick_mod(mat b,ll n,ll m,ll p)
{
    mat t;
    t.set();
    for(ll i=0; i<n; i++) t.t[i][i]=1;
    while(m)
    {
        if(m&1)
        {
            t=multiple(t,b,n,p);
        }
        m>>=1;
        b=multiple(b,b,n,p);
    }
    return t;
}

void init(ll k)
{
    b.set();
    for(ll i=0; i<k; i++)
        b.t[i][0]=1;
    for(ll i=1; i<k; i++)
    {
        for(ll j=i-1; j<k; j++)
            if(j==i-1)
                b.t[j][i]=k-i+1;
            else b.t[j][i]=1;
    }
    /*
      for(int i=0;i<k;i++)
      {
          for(int j=0;j<k;j++)
            printf("%lld ",b.t[i][j]);
          puts("");
      }
     */
}


int main()
{
    int cas;
    ll n;
    ll k;
    scanf("%d",&cas);
    for(int ca=1; ca<=cas; ca++)
    {
        scanf("%lld%lld",&n,&k);
        init(k);
        a=quick_mod(b,k,n-1,mod);
        ll ans=0;
        for(ll i=0; i<k; i++)
        {
            ans=(ans+(k+1)*a.t[0][i])%mod;
        }
        printf("Case #%d: %lld\n",ca,ans);
    }
    return 0;
}
/*
北京邀请赛的题目，当时是学长A的，也从那时候开始，我知道了还有矩阵快速幂这个东西。
然后回到学校，就学习了一下，感觉主要就是dp公式的求解最重要了，其他的套模版就ok。

首先来说一下这道题目的题意：定义一个字符串，它的任意字串都不能存在0-k的任意全排列，
那么我们称这样的字符串为elegant string。
接下里我们定义一个函数F(n,k)为字符长度为n，使用0-k的字母来构成elegant string的数目。

因为n很大，所以很容易想到要使用矩阵快速幂来加速。
那么接下来就是推导公式了。
我们定义dp[i][j]为长度为i，尾部j个字母均不相同的字符串的数目。
那么我们很容易推出dp[i][j]的递推公式了:
dp[i][j]=dp[i-1][j-1]*(k-j+2)+dp[i-1][j]+……+dp[i-1][k];
这是什么意思呢？
首先我们知道，dp[i]和dp[i-1]只差一个字母，假设我们在dp[i-1]后面加上一个字母，这个
字母可以是和dp[i-1]尾部几个不同的字母中的一个相同，也可以不同（例：假如dp[i-1]=……0123,
k=7,这是我们为了构成dp[i],我们可以在尾部加上4、5、6、7，或者0、1、2、3）
大家会发现如果是4、5、6、7，那么dp[i-1][j-1]就变成了dp[i][j](看定义),
如果是0、1、2、3，那么dp[i-1][j-1]就会相应变成dp[i][j],dp[i][j-1],dp[i][j-2],dp[i][j-3],
综上我们为了构成dp[i][j],就可以使用dp[i-1][j-1]---dp[i-1][k]来构造。
然后剩下的事就是构造矩阵了，很简单，不赘述。

转载请注明出处，谢谢。
*/


    联系
    我们