結果
| 問題 | No.840 ほむほむほむら |
| ユーザー |
 WA_TLE
|
| 提出日時 | 2019-06-14 22:33:01 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,807 bytes |
| コンパイル時間 | 1,276 ms |
| コンパイル使用メモリ | 133,876 KB |
| 実行使用メモリ | 8,760 KB |
| 最終ジャッジ日時 | 2023-08-09 01:49:39 |
| 合計ジャッジ時間 | 11,010 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
7,588 KB |
| testcase_01 | AC | 21 ms
4,380 KB |
| testcase_02 | AC | 298 ms
4,380 KB |
| testcase_03 | AC | 2,766 ms
4,380 KB |
| testcase_04 | AC | 2 ms
4,380 KB |
| testcase_05 | AC | 3 ms
4,376 KB |
| testcase_06 | AC | 41 ms
4,376 KB |
| testcase_07 | AC | 692 ms
4,380 KB |
| testcase_08 | TLE | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
ソースコード
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=998244353;
const llint big=2.19e17+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
//行列 h,m,r,hm,mr,hmr 3125^2*log
using hom=array<llint,3126>;
int K;
hom rui(hom A,hom B){
int i,j,x;
int AL=A[3125];
int BL=B[3125];
hom ans={};
for(i=0;i<K*K*K*K*K;i++){
x=i;
int Ah=x%K;x/=K;
int Am=x%K;x/=K;
int Ar=(AL+K+K-Ah-Am)%K;
int Ahm=x%K;x/=K;
int Amr=x%K;x/=K;
int Ahmr=x;
for(j=0;j<K*K*K*K*K;j++){
x=j;
int Bh=x%K;x/=K;
int Bm=x%K;x/=K;
int Br=(BL+K+K-Bh-Bm)%K;
int Bhm=x%K;x/=K;
int Bmr=x%K;x/=K;
int Bhmr=x;
int Ch=(Ah+Bh)%K;
int Cm=(Am+Bm)%K;
int Cr=(Ar+Br)%K;
int Chm=(Ahm+Bhm+Ah*Bm)%K;
int Cmr=(Amr+Bmr+Am*Br)%K;
int Chmr=(Ahmr+Bhmr+Ah*Bmr+Ahm*Br)%K;
ans[((((Chmr*K+Cmr)*K+Chm)*K+Cm)*K+Ch)]+=A[i]*B[j];
ans[((((Chmr*K+Cmr)*K+Chm)*K+Cm)*K+Ch)]%=mod;
}
}
//cerr<<"de";
ans[3125]=(AL+BL)%K;
return ans;
}
int main(void){
int n;cin>>n>>K;
hom bgen={},ans={};
bgen[1]=1;
bgen[K]=1;
bgen[0]=1;
bgen[3125]=1;
ans[0]=1;
while(n>0){
if(n%2){ans=rui(ans,bgen);}
bgen=rui(bgen,bgen);
//for(int i=0;i<K*K*K*K*K;i++){cerr<<bgen[i]<<" ";}cerr<<endl;
n/=2;
}
//for(int i=0;i<K*K*K*K*K;i++){cerr<<ans[i]<<" ";}cerr<<endl;
llint ret=0;
for(int i=0;i<K*K*K*K;i++){ret+=ans[i];ret%=mod;}
cout<<ret<<endl;
return 0;
}
/*
1357
ECA9
6824
B0FD
*/