結果

問題 No.840 ほむほむほむら
ユーザー WA_TLEWA_TLE
提出日時 2019-06-14 22:33:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,807 bytes
コンパイル時間 1,405 ms
コンパイル使用メモリ 136,320 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-11-14 07:00:29
合計ジャッジ時間 41,955 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,272 KB
testcase_01 AC 22 ms
10,280 KB
testcase_02 AC 298 ms
10,276 KB
testcase_03 AC 2,757 ms
10,276 KB
testcase_04 AC 3 ms
10,272 KB
testcase_05 AC 2 ms
10,148 KB
testcase_06 AC 42 ms
10,276 KB
testcase_07 AC 691 ms
13,636 KB
testcase_08 TLE -
testcase_09 AC 42 ms
6,816 KB
testcase_10 AC 3 ms
6,824 KB
testcase_11 AC 80 ms
6,820 KB
testcase_12 AC 1,084 ms
6,816 KB
testcase_13 TLE -
testcase_14 AC 1,329 ms
6,816 KB
testcase_15 AC 4 ms
6,816 KB
testcase_16 AC 122 ms
6,816 KB
testcase_17 AC 2,458 ms
6,820 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 10 ms
6,816 KB
testcase_22 AC 199 ms
6,816 KB
testcase_23 TLE -
testcase_24 AC 143 ms
6,816 KB
testcase_25 AC 2 ms
6,820 KB
testcase_26 AC 297 ms
6,816 KB
testcase_27 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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
*/
0