結果

問題 No.840 ほむほむほむら
ユーザー WA_TLE
提出日時 2019-06-14 22:33:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,807 bytes
コンパイル時間 1,228 ms
コンパイル使用メモリ 131,172 KB
最終ジャッジ日時 2025-01-07 04:34:52
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 18 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

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