e827 - 2.道路鋪設 (Roads)
題目描述
題目要求計算長度為 L 的道路，使用長度為 1, 2, 3, ..., L 的磁磚鋪滿的鋪法總數，並將結果模 10^9 + 7。
解題思路
這題可以利用動態規劃的思想來解決。設 dp[i] 表示長度為 i 的道路的鋪法總數。那麼，dp[i] 可以通過以下方式計算：
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-i]。
由於題目中 L 的範圍較大，直接使用迴圈計算會超時。觀察題目，可以發現題目要求的是斐波那契數列的變形。
題目要求計算 dp[L-1] mod 10^9 + 7。
程式碼中使用了遞迴和模運算來計算結果。mod() 函數用於計算模 10^9 + 7 的結果。
複雜度分析
- 時間複雜度: O(L)
- 空間複雜度: O(1)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline long long int mod(long long int p){
if(p<=1)return p+1;
bool o=p&1;
p>>=1;
long long int tmp=mod(p);
if(o)
return tmp*tmp*2%1000000007;
else
return tmp*tmp%1000000007;
}
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
long long int stk[12],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
long long int p(read());
while(p=read()){
write(mod(p-1));
putchar_unlocked('\n');
}
}