2019牛客多校第二场B
先保存一下代码。
/*Q:每次可以走1-k步，起点为0，问经过n点的概率 （n<=1e18,t<=10,k<1021）
dp[i]=(dp[i-1]+dp[i-2]+....+dp[i-k])/k;
n-> oo,p=2/(k+1)
证明：走k步期望走出的距离是 1+2+...+k =k(1+k)/2
也就是每段k(k+1)/2中，每个点被踩到的概率是 k/(k(k+1)/2)=2/(k+1)
所以无穷远处的点被踩到的概率就是2/(k+1)
考虑暴力，复杂度nk ，tle
考虑矩阵快速幂，复杂度k^3logn,tle
bm线性递推 k^2logn，ac
*/
#include<cstdio>
#include <algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define maxn 10015
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-7
#define mod 1000000007
typedef vector<ll>VI;
ll ff[maxn];
ll fastpow(ll x,ll y){
ll ans,res;
ans=1;res=x;
while(y){
if(y&1)ans=ans*res%mod;
res=res*res%mod;
y>>=1;
}
return ans ;
}
void init(){
for(int i=1;i<maxn;i++)ff[i]=fastpow(i,mod-2);
}
// head
namespace giao{
ll res[maxn],cc[maxn],mmd[maxn],base[maxn];
vector<int >md;
void mul(ll *a, ll *b,ll k){//矩阵的乘法
for(ll i=0;i<2*k;i++)cc[i]=0;
for(ll i=0;i<k;i++)
if(a[i])
for(int j=0;j<k;j++)
cc[i+j]=(cc[i+j]+a[i]*b[j])%mod;
for(ll i=2*k-1;i>=k;i--)
if(cc[i])
for(int j=0;j<md.size();j++)
cc[i-k+md[j]]=(cc[i-k+md[j]]-cc[i]*mmd[md[j]])%mod;
for(int i=0;i<k;i++)a[i]=cc[i];
}
ll solve(ll n,VI a,VI b){//传进来要求的第n项，然后抄就完了
ll ans,pnt;
ans=pnt=0;
ll k=a.size();//一开始自己算出来的前2k项
assert(a.size()==b.size());
for(int i=0;i<k;i++)mmd[k-1-i]=-a[i];
mmd[k]=1;
md.clear();
for(int i=0;i<k;i++){
if(mmd[i])md.push_back(i);
res[i]=base[i]=0;
}
res[0]=1;
while((1ll<<pnt)<=n)pnt++;
for(ll p=pnt;p>=0;p--){
mul(res,res,k); //
if((n>>p)&1){
for(ll i=k-1;i>=0;i--)res[i+1]=res[i];
res[0]=0;
for(int j=0;j<md.size();j++)
res[md[j]]=(res[md[j]]-res[k]*mmd[md[j]])%mod;
}
}
for(int i=0;i<k;i++)ans=(ans+res[i]*b[i])%mod;
if(ans<0)ans+=mod;
return ans;
}
VI bm(VI s){ //不管这个是什么，抄就完了
VI C(1,1),B(1,1);
ll l,m,b;
l=0;m=b=1;
for(int n=0;n<s.size();n++){
ll d=0;
for(int i=0;i<l+1;i++)d=(d+C[i]*s[n-i])%mod;
if(d==0)m++;
else if(2*l<=n){
VI T=C;
ll c=mod-d*fastpow(b,mod-2)%mod;
while(C.size()<B.size()+m)C.push_back(0);
for(int i=0;i<B.size();i++)C[i+m]=(C[i+m]+c*B[i])%mod;
l=n+1-l;
B=T;
b=d;
m=1;
}else{
ll c=mod-d*fastpow(b,mod-2)%mod;
while(C.size()<B.size()+m)C.push_back(0);
for(int i=0;i<B.size();i++)C[i+m]=(C[i+m]+c*B[i])%mod;
m++;
}
}
return C;
}
ll work( VI a,ll n){//传进来一个vector和要走到的位置
VI c=bm(a); //bm算法 ，传进去我自己算出来的前2k个数据吧。
c.erase(c.begin()); //不知道干什么的，抄。
for(int i=0;i<c.size();i++)c[i]=(mod-c[i])%mod; //不知道干什么的
return solve(n,c,VI(a.begin(),a.begin()+c.size())); // 第三个元素是原本的2k个加上了后来bm算出来的东西
}
}
void gao(){
ll k,n;
scanf("%lld%lld",&k,&n);
if(n==0){//走过原点的概率
printf("1\n");
return ;
}
if(n==-1){//无穷远
printf("%lld\n",2*ff[k+1]%mod);
return ;
}
vector<ll>v;
vector<ll>dp(3*k,0);
dp[0]=1;//走到i点的概率
v.push_back(1);
for(int i=1;i<=k;i++){ //前i个点走到的概率
for(int j=0;j<i;j++)dp[i]=(dp[i]+dp[j])%mod;//dp[i]=(dp[i-1]+dp[i-2]+....+dp[i-k])/k;
dp[i]=dp[i]*ff[k]%mod;
v.push_back(dp[i]); //塞进v数组里面
}
//现在v数组里面有k+1个数，分别表示走到0-k位置的概率
for(ll i=k+1;i<=2*k;i++){ //再算k个
for(int j=1;j<=k;j++)
dp[i]=(dp[i]+dp[i-j])%mod;
dp[i]=dp[i]*ff[k]%mod;
v.push_back(dp[i]);
}
//现在v数组里面有2k+1个数，分别表示走到0-2k的概率
ll ans=giao::work(v,n);
printf("%lld\n",ans);
}
int main(){
int t;
scanf("%d",&t);
init();
while(t--){
gao();
}
}
/*
4 9
2 8
1 1
3 4
5 100
*/
查看1道真题和解析