e679 - 11115 - Uncle Jack
題目描述
題目要求計算將 D 張 CD 分配給 N 個侄子的方法數。由於 CD 數量可能較大，直接計算組合數可能會導致溢位。
解題思路
題目本質上要求計算 N^D 的值。由於 N 和 D 的範圍可能導致結果超出標準整數類型，因此需要使用陣列來模擬大數的運算。程式碼使用一個大小為 51 的整數陣列 ans 來儲存大數的每一位數字。程式碼首先初始化 ans[0] 為 1。然後，進行 D 次迭代，每次迭代將 ans 陣列中的每個元素乘以 N，並處理進位。最後，從陣列的最高有效位開始，輸出大數的每一位數字。
複雜度分析
- 時間複雜度: O(D * 51) ，其中 D 是 CD 的數量。由於陣列大小固定為 51，可以簡化為 O(D)。
- 空間複雜度: O(1) ，因為陣列
ans的大小是固定的，不依賴於輸入大小。
程式碼
#include <iostream>
using namespace std;
int ans[51];
int main(){
int N,D,it;
while(cin >> N >> D){
if(!N)break;
for(int i=0;i<51;++i)
ans[i]=0;
ans[0]=1;
while(D--){
for(int i=0;i<51;++i)
ans[i]*=N;
for(int i=0;i<51;++i){
if(ans[i]>9){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
}
}
for(int i=50;i>=0;--i)
if(ans[i]){
it=i+1;
break;
}
while(it--)
cout << ans[it];
cout << "\n";
}
}