結果

問題 No.3080 Colonies on Line
ユーザー 沙耶花
提出日時 2025-03-28 22:25:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,730 bytes
コンパイル時間 4,988 ms
コンパイル使用メモリ 263,840 KB
実行使用メモリ 28,388 KB
最終ジャッジ日時 2025-03-28 22:26:42
合計ジャッジ時間 67,043 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000000
#define Inf64 1000000000000000001LL
vector<mint> mul(vector<mint> a,vector<mint> b){
	/*
	vector<mint> c(a.size()+b.size()-1,0);
	rep(i,a.size()){
		rep(j,b.size()){
			c[i+j] += a[i]*b[j];
		}
	}
	return c;
	*/
	return convolution(a,b);
}

mint Bostan_Mori(vector<mint> a,vector<mint> c,long long n){
	
	while(a.size()>=c.size())c.push_back(0);
	
	while(n!=0){
		auto cinv = c;
		for(int i=1;i<cinv.size();i+=2)cinv[i] *= -1;
		a = mul(a,cinv);
		c = mul(c,cinv);
		
		{
			vector<mint> na;
			for(int i=(n&1LL);i<a.size();i+=2)na.push_back(a[i]);
			swap(a,na);
		}
		{
			vector<mint> nc;
			for(int i=0;i<c.size();i+=2)nc.push_back(c[i]);
			swap(c,nc);
		}
		
		n>>=1;
	}
	return a[0];
}

void solve2(int N,int K){
	vector dp(N,vector<mint>(2,0));
	rep(i,N){
		dp[i][0]++;
		if(i-K-1>=0)dp[i][0] += dp[i-K-1][1];
		if(i>0)dp[i][1] += dp[i-1][0] + dp[i-1][1];
		if(i-K-1>=0)dp[i][1] -= dp[i-K-1][0] + dp[i-K-1][1];
		rep(j,2){
			if(i!=0)dp[i][j] += dp[i-1][j];
		}
	}
	mint ans = 0;
	rep(i,N){
		if(i==0)continue;
		ans += dp[i][1]-dp[i-1][1];;
	}
	ans++;
	cout<<ans.val()<<endl;
}

int main(){
	long long N,K;
	cin>>N>>K;
	
	if(N<=500000){
		solve2(N,K);
		return 0;
	}
	vector<mint> t(K*3+1);
	t[0]++;
	mint ans = 0;
	rep(i,K){
		long long x = i+K+1;
		if(x > N-1){
			ans++;
		}
		else{
			t[x+1] --;
		}
	}
	t = convolution(t,t);
	vector<mint> ff(K*2+2);
	ff[0] = 1;
	ff[1] -= 2;
	ff[K*2+1] ++;
	
	mint res = Bostan_Mori(t,ff,N);
	//cout<<res.val()<<endl;
	res -= ans;
	cout<<res.val()<<endl;
	return 0;
}
0