#include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin>>n>>k; long long A[n+1]; A[0] = 1; A[1] = 0; A[2] = (long long)k; int mod = 1000000007; for (int i = 3; i <= n; i++){ A[i] = (A[i-1]*k)%mod + (A[i-2]*(k-1))%mod; A[i] %= mod; } cout<<A[n]<<endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin>>n>>k; long long A[n+1]; A[0] = 1; A[1] = 0; A[2] = (long long)k; int mod = 1000000007; for (int i = 3; i <= n; i++){ A[i] = (A[i-1]*k)%mod + (A[i-2]*(k-1))%mod; A[i] %= mod; } cout<<A[n]<<endl; } |