本文共 1673 字，大约阅读时间需要 5 分钟。
f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d,
可以用矩阵进行优化，直接构造矩阵，然后快速幂即可。
#include#include #include #include #include #include #include #include #include #include #include #include #define INF 1000000001#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int MAXN = 20;struct Mat{ ll a[MAXN][MAXN]; void Init(){ memset(a,0,sizeof(a)); for(int i = 0; i < 20; i++){ a[i][i] = 1; } }};ll fa[MAXN],d[MAXN];ll n,k,MOD;Mat a;void Init(){ memset(a.a,0,sizeof(a.a)); for(int i = 0; i < n-1; i++){ a.a[i][i+1] = 1; } for(int i = 0; i < n; i++){ a.a[n-1][i] = fa[n - i - 1]; }}Mat Matadd(Mat a,Mat b){ Mat c; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ c.a[i][j] = (a.a[i][j] + b.a[i][j])%MOD; } } return c;}Mat Matmul(Mat a,Mat b){ Mat c; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ c.a[i][j] = 0; for(int k = 0; k < n; k++){ c.a[i][j] += (a.a[i][k] * b.a[k][j])%MOD; } c.a[i][j] %= MOD; } } return c;}Mat power(Mat a,ll n){ Mat c; c.Init(); while(n){ if(n & 1){ c = Matmul(c,a); } a = Matmul(a,a); n >>= 1; } return c;}int main(){ #ifndef ONLINE_JUDGE freopen("data","r",stdin); #endif while(~scanf("%lld%lld%lld",&n,&k,&MOD)){ if(!n && !k && !MOD)break; for(int i = 0; i < n; i++){ scanf("%lld",&fa[i]); fa[i] %= MOD; } for(int i = 0; i < n; i++){ scanf("%lld",&d[i]); d[i] %= MOD; } Init(); a = power(a,k-1); ll ans = 0; for(int i = 0; i < n; i++){ ans += a.a[0][i] * d[i] % MOD; ans %= MOD; } printf("%lld\n",ans); } return 0;}
转载于:https://www.cnblogs.com/sweat123/p/5440183.html