$zoj\ 3216$

题目大意

给出$n$，$k$，$(1 \leq n \leq 10^9,1 \leq k \leq 30)$。$f_n$表示将$n$分为数个不小于$k$的正整数的和的方案数，数字相同顺序不同的方案不算同一个，求$f_n$。

解

讨论方案的第一个数$x$，有

$$ f_n= \left\{ \begin{array}{ll} f_{n-1} & \textrm{if $x>k$} \\ f_{n-k} & \textrm{if $x=k$} \end{array} \right. $$

$\therefore f_i=f_{i-1}+f_{i-k}$。

构造$\mathrm{F(i)}$，$\mathrm{R}$。

$$ \mathrm{F(i)}= \left( \begin{array}{cccc} f_i & f_{i-1} & \ldots & f_{i-k+1} \end{array} \right) $$

$$ \mathrm{R}= \left( \begin{array}{ccccc} 1 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \ldots & 0\\ 0 & 0 & 0 & \ddots & 0\\ \vdots & \vdots & \vdots & \ldots & 1\\ 1 & 0 & 0 & 0 & 0 \end{array} \right) $$

$$ n_0=k, \mathrm{F(k)}= \left( \begin{array}{cccc} 1 & 0 & \ldots & 0 \end{array} \right) $$

Code

#include <cstdio>
#include <cstring>
#define rep(i,x,y) for (int i=x; i<=y; ++i)

typedef long long ll;
const ll mod=1000000007;
struct mat
{
    int n,m;
    ll v[35][35];
    mat(){}
    mat(int a,int b):n(a),m(b)
    {
        memset(v,0,sizeof(v));
    }
    ll *operator [] (int x)
    {
        return v[x];
    }
} r,s;
int n,m,tc;

inline void operator *= (mat &a,mat b)
{
    ll t[35];
    rep(i,0,a.n)
    {
        memset(t,0,sizeof(t));
        rep(j,0,a.m)
            rep(k,0,a.m)
                t[j]=(t[j]+a[i][k]*b[k][j]%mod)%mod;
        memcpy(a[i],t,sizeof(t));
    }
}

int main()
{
    for (scanf("%d",&tc); tc--;)
    {
        scanf("%d%d",&n,&m),--m;
        if (n<=m)
        {
            puts("0");
            continue;
        }
        r=mat(m,m),++r[0][0],++r[m][0];
        rep(i,1,m)
            r[i-1][i]=1;
        s=mat(0,m),s[0][0]=1;
        for (int i=n-m-1; i; i>>=1,r*=r)
            if (i&1)
                s*=r;
        printf("%lld\n",s[0][0]);
    }
    return 0;
}