题目相关

题目链接：CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）——E

题目描述：

JWJU的桌游协会经常在课余时间组织大家玩飞行棋游戏，来促进同学们之间的友♂谊。
飞行棋的规则如下：
1、每名玩家有一个棋子，每个回合可以掷一次骰子。
2、如果使用的骰子为$k$面，则这$k$面上的点数分别为$1,2,3,\ldots,k$，且掷得每种点数的概率均为$\frac{1}{k}$。
3、如果当前回合掷得的点数为$Q$，则玩家控制的棋子前进$Q$步。
4、若当前棋子的位置到终点的距离$d<Q$，则棋子先行动$d$步到终点，再倒退$Q-d$步。（即到终点的距离变为$Q-d$）
5、某一回合结束后，若该玩家的棋子恰好到达终点，则宣布胜利。
璇璇姐姐参与了这个游戏，已知现在她的棋子到终点的距离为$d$，游戏使用的骰子有$k$面，求璇璇获得胜利需要的回合数期望。

输入输出格式：

输入格式：
两个正整数$d$和$k$，分别代表璇璇的棋子到终点的距离$d$以及骰子的面数$k$。
输出格式：
输出$x \times y^{-1} \bmod 1000000007(1000000007 = 10^9+7)$，其中$y^{-1}$表示$y$在模$1000000007$意义下的乘法逆元。
注：可以证明此题答案可以表示为有理数$\frac{x}{y}$，且$x,y$互质。保证在本题数据范围内，$y$的乘法逆元一定存在。

输入输出样例：

输入	输出
6 6	6

说明：

$1\le k \le d \le 10^{18}, 1 \le k \le 20$

博主乱搞

蒟蒻解析

博主习惯把d看成n如果打成n了也就是d的意思。。。
~~不愿意做ACM的原因是他一点步骤分都没有。~~
很明显这是一个概率dp题。我们不妨先推一下公式。
分为两种情况考虑：d≤k和d大于k。
情况1——$d＞k$
不用考虑前进超过原点返回。我们从终点倒着走。
假设现在到终点的距离为x，那么他的期望则由在到终点[x-k,x-1]转移过来，每个概率都为$\frac{1}{k}$，而且要加上掷骰子的期望+1。也就是：
$$E_x=1+\frac{1}{k}\sum_{i=x-k}^{x-1}E_i$$
情况2——$d≤k$
可能会跑过。这里介绍两种处理思路。
思路（1）高斯消元思路
（好像好多大佬都是这么想的不过蒟蒻我没想到这么多）以下是引用jhy大佬的一段解释

因为k特别小，所以我们可以把 f(0) (显然是0)，f(1)，f(2)，…..，f(k-1) 暴力高斯消元出来 (这个你们不会的话可以试着把每个0<x<k的x的等式写出来，然后把f(x)项全移到左边，其他项全移到右边，就可以得到一个方程；这样可以列k-1个方程，正好k-1个未知数，高斯消元模板)。
jhy《CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）E 》

~~由于博主搞不太懂~~附上大佬文章链接
思路（2）直接看到底
由条件易知正好跳到终点的概率是$\frac{1}{k}$，而每一次跑过了之后的点到终点的距离仍然在k以内，也就是概率仍为$\frac{1}{k}$。
换句话说，在哪开始到终点概率都是$\frac{1}{k}$。
所以这部分期望就是k。

总结以上两种情况，可以得到状态转移方程：
\begin{eqnarray}E_x=
\begin{cases}
k&x≤k \cr
1+\frac{1}{k}\sum_{i=x-k}^{x-1}E_i\qquad&x>k\cr
\end{cases}
\end{eqnarray}

观察到d大的惊人。
我们就可以考虑矩阵加速了。
然后这道题就解决了。

蒟蒻代码

c++

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long 
const int maxn=30;
const ll mod=1000000007;
struct matrix{
    ll a[maxn][maxn];
    void clr(){
        memset(a,0,sizeof(a));
    }
};
matrix u,v,res;
matrix operator * (matrix aa,matrix bb){
    matrix tmp; memset(tmp.a,0,sizeof(tmp.a));
    ll tp=0;
    for (int i=1;i<maxn;++i){
        for (int j=1;j<maxn;++j){
            tp=0;
            for (int k=1;k<maxn;++k){
                tp=((tp+aa.a[i][k]*bb.a[k][j])%mod+mod)%mod;
                tmp.a[i][j]=tp;
            }
        }
    }
    return tmp;
}
matrix ksm_m(matrix aa,ll t){
    matrix tmp=aa; t--;
    while (t){
        if (t&1) tmp=tmp*aa;
        aa=aa*aa;
        t/=2;
    }
    return tmp;
}
ll d,k,nk;
ll ksm(ll x,ll t){
    ll res=1; x%=mod;
    while (t){
        if (t&1) res=res*x%mod;
        x=x*x%mod;
        t/=2;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&d,&k);
    nk=ksm(k,mod-2);
    if (d<=k){
        printf("%lld",k);
        return 0;
    }
    for (int i=1;i<=k;++i) u.a[i][1]=k;
    u.a[k+1][1]=1;
    for (int i=1;i<=k-1;++i) v.a[i][i+1]=1;
    for (int i=1;i<=k;++i) v.a[k][i]=nk;
    v.a[k][k+1]=v.a[k+1][k+1]=1;
    res=ksm_m(v,d-k); res=res*u;
    printf("%lld",res.a[k][1]);
    return 0;
}