problem
一只青蛙，他会跳，现在要从 \(1\) 跳到 \(n\)。跳一次有 \(m\) 种跳法，假设现在在 \(x\)，那么第 \(i\) 次可以从 \(x\) 跳到 \(x+d_i\)，同时消耗 \(p_j\) 的能量。问你有多少种跳的方案使得消耗能量不超过 \(k\)。\(n\leq 10^9,m\leq 10^5,1\leq d\leq 10,0\leq p,k\leq 400\)。15s,1G。
solution
矩阵乘法维护 \(10\) 个点的 DP 值，但是 DP 值是一个 \(\bmod x^{k+1}\) 的多项式，\([x^p]f_i\) 表示走了 \(i\) 步消耗 \(p\) 的能量的方案数。矩阵刻画后直接快速幂优化。\(O(10^3k^2\log n)\)。能过。
code
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const int P=1e9;
void red(LL&x){x%=P;}
int n,m,k;
vector<LL> multiple(vector<LL> a,vector<LL> b){
vector<LL> c(k+1,0);
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++) if(i+j<=k) red(c[i+j]+=a[i]*b[j]);
}
return c;
}
void pls(vector<LL>&a,vector<LL> b){
a.resize(k+1);
for(int i=0;i<b.size();i++) red(a[i]+=b[i]);
}
void multiple(vector<LL>a[15][15],vector<LL>b[15][15],vector<LL>c[15][15]){
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
for(int k=0;k<10;k++){
pls(c[i][k],multiple(a[i][j],b[j][k]));
}
}
}
}
void mulline(vector<LL>*a,vector<LL>b[15][15],vector<LL>*c){
for(int i=0;i<1;i++){
for(int j=0;j<10;j++){
for(int k=0;k<10;k++){
pls(c[k],multiple(a[j],b[j][k]));
}
}
}
}
vector<LL> a[32][15][15],ans[15],tmp[15];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<9;i++) a[0][i+1][i]={1};
for(int i=0;i<10;i++) a[0][i][9].resize(k+1);
for(int i=1;i<=m;i++){
int d,p;
scanf("%d%d",&d,&p);
a[0][10-d][9][p]++;
}
n--;
ans[9]={1};
for(int i=1;1<<i<=n;i++) multiple(a[i-1],a[i-1],a[i]);
for(int i=0;1<<i<=n;i++) if(n>>i&1){
mulline(ans,a[i],tmp);
for(int j=0;j<10;j++) ans[j]=tmp[j],tmp[j].clear();
}
LL res=0;
ans[9].resize(k+1);
for(int i=0;i<=k;i++) red(res+=ans[9][i]);
printf("%lld\n",res);
return 0;
}