我的解法是參考這個網站的想法
https://acm.cs.nthu.edu.tw/problem/10322/
我測資二 0.8S 測資三 1.5S
然而測資一一直超時,請求各位大老們幫忙!
以下是我的程式碼
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
void fun(unsigned long long int **matrix1,unsigned long long int **matrix2,unsigned long long int **matrix3,int n)
{
unsigned long long int sum=0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
for(int k=0;k<n;++k)
sum+=matrix1[i][k]*matrix2[k][j];
matrix3[i][j]=sum%MOD;
sum=0;
}
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
matrix1[i][j]=matrix3[i][j];
}
int main()
{
int number;
cin>>number;
for(int f=0;f<number;++f)
{
int n;
unsigned long long int k;
cin>>n>>k;
if(k<=n)
cout<<1<<endl;
else
{
//動態記憶體配置及宣告
int bit[51]={0},bit_count=0;
unsigned long long int power=k-n,sum=0;
unsigned long long int **matrix=new unsigned long long int *[n];
unsigned long long int **sum_matrix=new unsigned long long int *[n];
unsigned long long int **temp_matrix=new unsigned long long int *[n];
for(int i=0;i<n;++i)
{
matrix[i]=new unsigned long long int [n];
sum_matrix[i]=new unsigned long long int [n];
temp_matrix[i]=new unsigned long long int [n];
}
//初始化
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
if(i==0)
matrix[i][j]=1;
else if(j-i==-1)
matrix[i][j]=1;
else
matrix[i][j]=0;
if(i==j)
sum_matrix[i][j]=1;
else
sum_matrix[i][j]=0;
}
//把n-k轉乘2進位
for(int i=0;i<51;++i)
{
if(power%2==1)
bit[i]=1;
power/=2;
++bit_count; //可減短執行時間
if(power==0)
break;
}
//把matrix n次方
for(int i=0;i<bit_count;++i)
{
if(bit[i]==1)
fun(sum_matrix,matrix,temp_matrix,n);
fun(matrix,matrix,temp_matrix,n);
}
//算結果並輸出
for(int i=0;i<n;++i)
sum+=sum_matrix[0][i];
cout<<sum%MOD<<endl;
//釋放記憶體
for(int i=0;i<n;++i)
{
delete [] matrix[i];
delete [] sum_matrix[i];
delete [] temp_matrix[i];
}
delete [] matrix;
delete [] sum_matrix;
delete [] temp_matrix;
}
}
return 0;
}
fdhs109_GT
(GT coding)
學校
:
桃園市私立復旦高級中學
編號 : 102099
來源 : [140.114.217.85]
最後登入時間 ：
2024-03-27 01:07:43
哈，才提示你演算法，你就真的去做了，很棒呢～ ：）
題主的提示 ：
有時認為比較快的方法，反而比較慢；
有時認為比較慢的方法，反而比較快。
第一筆測資有 10000 筆，但測資最大只有 4999 (我去試出來的~)。
也就是說第一筆建表似乎會比較快，
可以試試看。
另外 2 進位的部分，
可以用位元運算 &, >>= 來寫，
power % 2 == 1 寫法等於 power & 1，
意思是 power 的二進位和 1 的二進位做 "&(且)" 的運算，
而 1 的二進位是 00000...1，
意思同於 % 2，
但 "模除(%)" 動作很慢，
建議少用，
而 >>= 是指位元右移，
e.g. 二進位的 100101 >>= 1 會變成 010010，
意思是全部的位元右移 1 。
這種方法會比較快(測資大的時候會很明顯)。
附上快速冪，
template <typename T>
inline T powi(T a, auto b) {
T re;
for(re = 1; b; b >>= 1, a *= a)
if(b & 1) re *= a;
return re;
}
把傳入參數改成矩陣，應該會比較直觀吧 ~:)。
以上，祝 解題順利，加油！
哈，才提示你演算法，你就真的去做了，很棒呢～ ：）
題主的提示 ：
有時認為比較快的方法，反而比較慢；
有時認為比較慢的方法，反而比較快。
第一筆測資有 10000 筆，但測資最大只有 4999 (我去試出來的~)。
也就是說第一筆建表似乎會比較快，
可以試試看。
另外 2 進位的部分，
可以用位元運算 &, >>= 來寫，
power % 2 == 1 寫法等於 power & 1，
意思是 power 的二進位和 1 的二進位做 "&(且)" 的運算，
而 1 的二進位是 00000...1，
意思同於 % 2，
但 "模除(%)" 動作很慢，
建議少用，
而 >>= 是指位元右移，
e.g. 二進位的 100101 >>= 1 會變成 010010，
意思是全部的位元右移 1 。
這種方法會比較快(測資大的時候會很明顯)。
附上快速冪，
template
inline T powi(T a, auto b) {
T re;
for(re = 1; b; b >>= 1, a *= a)
if(b & 1) re *= a;
return re;
}
把傳入參數改成矩陣，應該會比較直觀吧 ~:)。
以上，祝 解題順利，加油！
非常感謝大大的教導以及提供測資一的資訊
我把k<5000的都用建表來去算答案
而確實這樣會快非常多呢!(測資一的話)
也因此得以順利完成這題
再來是關於｢>>=｣這個運算子
>>=對於把十進位轉成二進位在哪方面能派上用場呢?
還是我對這個運算子的用途有所誤會!?
還請大大開導!
314159265358979323846264338327
...
(少年π)
學校
:
臺北市私立延平高級中學
編號 : 69058
來源 : [223.136.179.30]
最後登入時間 ：
2024-04-29 19:11:35
哈，才提示你演算法，你就真的去做了，很棒呢～ ：）
題主的提示 ：
有時認為比較快的方法，反而比較慢；
有時認為比較慢的方法，反而比較快。
第一筆測資有 10000 筆，但測資最大只有 4999 (我去試出來的~)。
也就是說第一筆建表似乎會比較快，
可以試試看。
另外 2 進位的部分，
可以用位元運算 &, >>= 來寫，
power % 2 == 1 寫法等於 power & 1，
意思是 power 的二進位和 1 的二進位做 "&(且)" 的運算，
而 1 的二進位是 00000...1，
意思同於 % 2，
但 "模除(%)" 動作很慢，
建議少用，
而 >>= 是指位元右移，
e.g. 二進位的 100101 >>= 1 會變成 010010，
意思是全部的位元右移 1 。
這種方法會比較快(測資大的時候會很明顯)。
附上快速冪，
template
inline T powi(T a, auto b) {
T re;
for(re = 1; b; b >>= 1, a *= a)
if(b & 1) re *= a;
return re;
}
把傳入參數改成矩陣，應該會比較直觀吧 ~:)。
以上，祝 解題順利，加油！
非常感謝大大的教導以及提供測資一的資訊
我把k<5000的都用建表來去算答案
而確實這樣會快非常多呢!(測資一的話)
也因此得以順利完成這題
再來是關於｢>>=｣這個運算子
>>=對於把十進位轉成二進位在哪方面能派上用場呢?
還是我對這個運算子的用途有所誤會!?
還請大大開導!
｢>>=｣就是將位元右移,在十進制就相當於把此數除以2並將它無條件捨去
ex:
11111111(2)=255(10)
255>>=1之後的結果是01111111(2) =127(10)
跟floor(255/2)=127是一樣的
補充:｢<<=｣就是將位元左移,在十進制就相當於把此數乘以2
fdhs109_GT
(GT coding)
學校
:
桃園市私立復旦高級中學
編號 : 102099
來源 : [140.114.217.85]
最後登入時間 ：
2024-03-27 01:07:43
314159265358979323846264338327
...
(少年π)
學校
:
臺北市私立延平高級中學
編號 : 69058
來源 : [223.136.179.30]
最後登入時間 ：
2024-04-29 19:11:35