e895 - 好多正方形
題目描述
題目要求計算在長度為 L 的通道上堆放正方形貨品的方式數，其中正方形的邊長為整數且不超過 L，且貨品不能相互堆疊。由於方案數可能很大，需要輸出方案數模 10007 的結果。
解題思路
這題可以利用動態規劃的思想來解決。設 dp[i] 表示在長度為 i 的通道上堆放正方形的方式數。我們可以遞歸地計算 dp[i]，考慮在長度為 i 的通道上放置一個邊長為 j 的正方形，其中 1 <= j <= i。放置一個邊長為 j 的正方形後，剩餘的通道長度為 i - j，因此剩餘通道的堆放方式數為 dp[i - j]。因此，dp[i] = sum(dp[i - j])，其中 1 <= j <= i。
由於題目要求輸出結果模 10007，因此在計算 dp[i] 時，需要對每次加法都取模 10007。
程式碼中 mod 函數用於計算 a-1 模 10007 的結果，利用快速冪的原理來加速計算。read 和 write 函數用於快速讀取和輸出整數。
複雜度分析
- 時間複雜度: O(L^2)
- 空間複雜度: O(L)
程式碼
#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 int mod(int y,int z){
if(y==0)return 1;
if(y==1)return 2;
bool o=y&1;
y>>=1;
int tmp=mod(y,z);
if(o)
return tmp*tmp*2%z;
else
return tmp*tmp%z;
}
inline int read(){
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) {
int stk[6],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int a;
while(a=read()){
write(mod(a-1,10007));
putchar_unlocked('\n');
}
}