結果

問題 No.3403 Count 1210 Sequence
コンテスト
ユーザー id-ord
提出日時 2025-12-10 19:59:00
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 851 ms / 2,000 ms
コード長 877 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,533 ms
コンパイル使用メモリ 661,244 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2025-12-10 19:59:41
合計ジャッジ時間 33,710 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
using namespace std;
constexpr int64_t p=998244353;
const vector<int64_t> ftbl=[]{vector<int64_t>ret(202501);ret[0]=1;for(int i=1;i<202501;i++){ret[i]=(ret[i-1]*i)%p;}return ret;}();
const vector<int64_t> invtbl=[]{vector<int64_t>ret(202501);ret[0]=1;ret[1]=1;for(int64_t i=2;i<202501;i++){ret[i]=p-((p-p%i)/i*ret[p%i])%p;}return ret;}();
const vector<int64_t> invftbl=[]{vector<int64_t>ret(202501);ret[0]=1;for(int i=1;i<202501;i++){ret[i]=(ret[i-1]*invtbl[i])%p;}return ret;}();
int f(int n,int r){return(ftbl[n]*int64_t(n-2*r+1)%p)*(invftbl[r]*invftbl[n-r+1]%p)%p;}
int main(){int T;cin>>T;while(T--){
	int N,A;cin>>N>>A;
	int64_t ans=0;
	for(int i=1;i*i<=A;i++){
		if(A%i!=0)continue;
		int r1=N-1-A/i,r2=N-1-i;
		if(r1>=0&&r1%2==0)ans+=f(N-1,r1/2);
		if(r2>=0&&r2%2==0&&r1!=r2)ans+=f(N-1,r2/2);ans%=p;
	}
	cout<<ans<<"\n";
}return 0;}
0