結果
| 問題 |
No.3182 recurrence relation’s intersection sum
|
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2025-06-13 22:08:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 8 ms / 2,000 ms |
| コード長 | 40,128 bytes |
| コンパイル時間 | 4,854 ms |
| コンパイル使用メモリ | 258,888 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-06-13 22:09:03 |
| 合計ジャッジ時間 | 5,720 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//入力が必ず-mod<a<modの時.
template<const int mod>
struct modint{ //mod変更が不可能.
public:
long long v = 0;
static void setmod(int m){} //飾り.
static constexpr long long getmod(){return mod;}
modint(){v = 0;} modint(int a){v = a<0?a+mod:a;} modint(long long a){v = a<0?a+mod:a;}
modint(unsigned int a){v = a;} modint(unsigned long long a){v = a;}
long long val()const{return v;}
modint &operator=(const modint &b) = default;
modint operator+()const{return (*this);}
modint operator-()const{return modint(0)-(*this);}
modint operator+(const modint b)const{return modint(v)+=b;}
modint operator-(const modint b)const{return modint(v)-=b;}
modint operator*(const modint b)const{return modint(v)*=b;}
modint operator/(const modint b)const{return modint(v)/=b;}
modint operator+=(const modint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
modint operator-=(const modint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
modint operator*=(const modint b){v = v*b.v%mod; return *this;}
modint operator/=(modint b){ //b!=0 mod素数が必須.
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
modint operator++(){*this += 1; return *this;}
modint operator--(){*this -= 1; return *this;}
modint operator++(int){*this += 1; return *this;}
modint operator--(int){*this -= 1; return *this;}
bool operator==(const modint b)const{return v == b.v;}
bool operator!=(const modint b)const{return v != b.v;}
bool operator>(const modint b)const{return v > b.v;}
bool operator>=(const modint b)const{return v >= b.v;}
bool operator<(const modint b)const{return v < b.v;}
bool operator<=(const modint b)const{return v <= b.v;}
modint pow(long long n)const{
modint ret = 1,p = v;
if(n < 0) p = p.inv(),n = -n;
while(n){
if(n&1) ret *= p;
p *= p; n >>= 1;
}
return ret;
}
modint inv()const{return modint(1)/v;} //素数mod必須.
};
template<int idx> //modが入力で与えられる場合.
struct dynamic_modint{ //mod変更が可能 最初にsetmod必須 idxで複数個所持が可能.
private:
static int mod;
public:
long long v = 0;
static constexpr long long getmod(){return mod;}
static void setmod(int m){
assert(m > 0);
mod = m;
}
dynamic_modint(){v = 0;}
dynamic_modint(int a){v = a<0?a+mod:a;} dynamic_modint(long long a){v = a<0?a+mod:a;}
dynamic_modint(unsigned int a){v = a;}
dynamic_modint(unsigned long long a){v = a;}
long long val()const{return v;}
dynamic_modint &operator=(const dynamic_modint &b) = default;
dynamic_modint operator+()const{return (*this);}
dynamic_modint operator-()const{return dynamic_modint(0)-(*this);}
dynamic_modint operator+(const dynamic_modint b)const{return dynamic_modint(v)+=b;}
dynamic_modint operator-(const dynamic_modint b)const{return dynamic_modint(v)-=b;}
dynamic_modint operator*(const dynamic_modint b)const{return dynamic_modint(v)*=b;}
dynamic_modint operator/(const dynamic_modint b)const{return dynamic_modint(v)/=b;}
dynamic_modint operator+=(const dynamic_modint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
dynamic_modint operator-=(const dynamic_modint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
dynamic_modint operator*=(const dynamic_modint b){v = v*b.v%mod; return *this;}
dynamic_modint operator/=(dynamic_modint b){ //b!=0 mod素数が必須.
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
dynamic_modint operator++(){*this += 1; return *this;}
dynamic_modint operator--(){*this -= 1; return *this;}
dynamic_modint operator++(int){*this += 1; return *this;}
dynamic_modint operator--(int){*this -= 1; return *this;}
bool operator==(const dynamic_modint b)const{return v == b.v;}
bool operator!=(const dynamic_modint b)const{return v != b.v;}
bool operator>(const dynamic_modint b)const{return v > b.v;}
bool operator>=(const dynamic_modint b)const{return v >= b.v;}
bool operator<(const dynamic_modint b)const{return v < b.v;}
bool operator<=(const dynamic_modint b)const{return v <= b.v;}
dynamic_modint pow(long long n)const{
dynamic_modint ret = 1,p = v;
if(n < 0) p = p.inv(),n = -n;
while(n){
if(n&1) ret *= p;
p *= p; n >>= 1;
}
return ret;
}
dynamic_modint inv()const{return dynamic_modint(1)/v;} //素数mod必須.
};
template<int idx> int dynamic_modint<idx>::mod=998244353;
using mint = modint<998244353>;
//using mint = modint<1000000007>;
//using mint = dynamic_modint<0>;
namespace to_fold{
__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}
pair<long long,long long> invgcd(long long a,long long b){
//return {gcd(a,b),x} (xa≡g(mod b))
a = safemod(a,b);
if(a == 0) return {b,0};
long long x = 0,y = 1,memob = b;
while(a){
long long q = b/a;
b -= a*q;
swap(x,y); y -= q*x;
swap(a,b);
}
if(x < 0) x += memob/b;
return {b,x};
}
template<long long mod>
long long Garner(const vector<long long> &A,const vector<long long> &M){
__int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.
for(int i=1; i<A.size(); i++){
//assert(gcd(mulM,M.at(i-1)) == 1);
mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_t
long long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));
x += t*mulM;
}
return x%mod;
}
int countzero(unsigned long long x){
if(x == 0) return 64;
else return __popcount((x&-x)-1);
}
template<typename mint>
struct fftinfo{
static bool First;
static mint g,sum_e[30],sum_ie[30]; //sum_e[i]=Π[j=0~i-1]ies[j] * es[i],sum_ie[i]=Π[i=0~j-1]es[j] * ies[i].
static mint divpow2[30]; //div[i] = 1/(2^i).
static mint Zeta[30];
fftinfo(){
if(!First) return;
First = false;
const long long mod = mint::getmod();
if(mod == 998244353) g = 3;
else if(mod == 754974721) g = 11;
else if(mod == 167772161) g = 3;
else if(mod == 469762049) g = 3;
else assert(false); //現状RE.
mint es[30],ies[30]; //es[i]^(2^(2+i))=1.
int cnt2 = countzero(mod-1);
mint e = g.pow((mod-1)>>cnt2),ie = e.inv();
for(int i=cnt2; i>=2; i--){ //e^(2^i)=1;
es[i-2] = e,e *= e;
ies[i-2] = ie,ie *= ie;
}
mint rot = 1;
for(int i=0; i<=cnt2-2; i++) sum_e[i] = es[i]*rot,rot *= ies[i];
rot = 1;
for(int i=0; i<=cnt2-2; i++) sum_ie[i] = ies[i]*rot,rot *= es[i];
mint div2n = 1,div2 = mint(1)/2;
for(int i=0; i<30; i++) divpow2[i] = div2n,div2n *= div2;
for(int i=0; i<=cnt2; i++) Zeta[i] = g.pow((mod-1)/(2<<i));
}
};
template<typename mint> bool fftinfo<mint>::First=true;
template<typename mint> mint fftinfo<mint>::g;
template<typename mint> mint fftinfo<mint>::sum_e[30];
template<typename mint> mint fftinfo<mint>::sum_ie[30];
template<typename mint> mint fftinfo<mint>::divpow2[30];
template<typename mint> mint fftinfo<mint>::Zeta[30];
template<typename mint>
void NTT(vector<mint> &A){ //ACLを超参考にしてる.
int n = A.size();
assert((n&-n) == n);
fftinfo<mint> info;
int h = countzero(n);
for(int ph=1; ph<=h; ph++){
int w = 1<<(ph-1),p = 1<<(h-ph);
mint rot = 1;
for(int s=0; s<w; s++){
int offset = s<<(h-ph+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
A.at(i+offset) = l+r;
A.at(i+offset+p) = l-r;
}
rot *= info.sum_e[countzero(~(unsigned int)(s))];
}
}
}
template<typename mint>
void INTT(vector<mint> &A){
int n = A.size();
assert((n&-n) == n);
fftinfo<mint> info;
const unsigned int mod = mint::getmod();
int h = countzero(n);
for(int ph=h; ph>0; ph--){
int w = 1<<(ph-1),p = 1<<(h-ph);
mint irot = 1;
for(int s=0; s<w; s++){
int offset = s<<(h-ph+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p);
A.at(i+offset) = l+r;
A.at(i+offset+p) = ((unsigned long long)(mod+(unsigned int)l.v-(unsigned int)r.v)*irot.v)%mod;
}
irot *= info.sum_ie[countzero(~(unsigned int)(s))];
}
}
mint divn = info.divpow2[h];
for(auto &a : A) a *= divn;
}
template<typename mint>
vector<mint> convolution(vector<mint> A,vector<mint> B){ //mintじゃないのを突っ込まないように!!!.
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
if(siza == 0 || sizb == 0) return {};
if(min(siza,sizb) <= 60){ //naive.
vector<mint> ret(sizc);
if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
return ret;
}
while(N < sizc) N <<= 1;
A.resize(N),B.resize(N);
NTT(A); NTT(B);
for(int i=0; i<N; i++) A.at(i) *= B.at(i);
INTT(A); A.resize(sizc);
return A;
}
vector<long long> convolution_ll(const vector<long long> &A,const vector<long long> &B){ //long longに収まる範囲.
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
vector<long long> ret(sizc);
if(min(siza,sizb) <= 200){ //naive 200はやばい?.
vector<long long> ret(sizc);
if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
return ret;
}
const unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
const unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;
const unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;
assert(sizc <= (1<<24));
using mint1 = modint<mod1>;
using mint2 = modint<mod2>;
using mint3 = modint<mod3>;
vector<mint1> a1(siza),b1(sizb);
vector<mint2> a2(siza),b2(sizb);
vector<mint3> a3(siza),b3(sizb);
for(int i=0; i<siza; i++) a1.at(i) = A.at(i)%mod1;
for(int i=0; i<sizb; i++) b1.at(i) = B.at(i)%mod1;
vector<mint1> C1 = convolution(a1,b1);
for(int i=0; i<siza; i++) a2.at(i) = A.at(i)%mod2;
for(int i=0; i<sizb; i++) b2.at(i) = B.at(i)%mod2;
vector<mint2> C2 = convolution(a2,b2);
for(int i=0; i<siza; i++) a3.at(i) = A.at(i)%mod3;
for(int i=0; i<sizb; i++) b3.at(i) = B.at(i)%mod3;
vector<mint3> C3 = convolution(a3,b3);
vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};
for(int i=0; i<sizc; i++){
unsigned long long x = 0;
x += (C1.at(i).v*i1)%mod1*m2m3;
x += (C2.at(i).v*i2)%mod2*m3m1;
x += (C3.at(i).v*i3)%mod3*m1m2;
long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;
if(diff < 0) diff += mod1;
x -= offset.at(diff%5);
ret.at(i) = x;
}
return ret;
}
template<typename mint>
vector<mint> convolution_llmod(const vector<mint> &A,const vector<mint> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
vector<mint> ret(sizc);
if(min(siza,sizb) <= 200){
for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);
return ret;
}
const long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
assert(sizc <= (1<<24));
using mint1 = modint<mod1>;
using mint2 = modint<mod2>;
using mint3 = modint<mod3>;
vector<mint1> a1(siza),b1(sizb);
vector<mint2> a2(siza),b2(sizb);
vector<mint3> a3(siza),b3(sizb);
for(int i=0; i<siza; i++) a1.at(i) = A.at(i).v%mod1;
for(int i=0; i<sizb; i++) b1.at(i) = B.at(i).v%mod1;
vector<mint1> C1 = convolution(a1,b1);
for(int i=0; i<siza; i++) a2.at(i) = A.at(i).v%mod2;
for(int i=0; i<sizb; i++) b2.at(i) = B.at(i).v%mod2;
vector<mint2> C2 = convolution(a2,b2);
for(int i=0; i<siza; i++) a3.at(i) = A.at(i).v%mod3;
for(int i=0; i<sizb; i++) b3.at(i) = B.at(i).v%mod3;
vector<mint3> C3 = convolution(a3,b3);
for(int i=0; i<sizc; i++){
vector<long long> A = {C1.at(i).v,C2.at(i).v,C3.at(i).v};
vector<long long> M = {mod1,mod2,mod3};
ret.at(i) = Garner<mint::getmod()>(A,M);
}
return ret;
}
vector<int> convolution_int(const vector<int> &A,const vector<int> &B){ //intに収まる範囲.
if(A.size() == 0 || B.size() == 0) return {};
vector<int> ret;
if(min(A.size(),B.size()) <= 60){
ret.resize(A.size()+B.size()-1);
for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
}
else{
using mint1 = modint<998244353>;
vector<mint1> X(A.size()),Y(B.size()),Z;
for(int i=0; i<A.size(); i++) X.at(i) = A.at(i);
for(int i=0; i<B.size(); i++) Y.at(i) = B.at(i);
Z = convolution(X,Y);
ret.resize(Z.size());
for(int i=0; i<Z.size(); i++) ret.at(i) = Z.at(i).v;
}
return ret;
}
template<typename mint>
void NTTdoubling(vector<mint> &A){ //NTTの原理を忘れているため何やってるのか意味が分からない NTT-friendly専用.
//INTT->resize(2倍）->NTTの代わりにcopy->INTT->謎の操作->NTT->push sizeが小さい時は効率悪いらしいよ.
int n = A.size();
fftinfo<mint> info;
vector<mint> B = A;
INTT(B);
mint rot = 1,zeta = info.Zeta[countzero(n)];
for(auto &v : B) v *= rot,rot *= zeta;
NTT(B); A.reserve(n<<1);
for(auto &v : B) A.push_back(v);
}
bool isNTTfriendly(long long mod){
if(mod == 998244353 || mod == 754974721 || mod == 16777216 || mod == 469762049) return true;
return false; //現状false 原子根求める機能を追加してから.
int have2 = countzero(mod-1);
return have2 >= 20;//とりあえず2^20でokとする;
}
}
using namespace to_fold;
template<typename T> //実質mintだけ?.
struct FormalPowerSeries:vector<T>{ //NTT-friendly素数だけ じゃなくてもいいけど全部書き直せ!.
using vector<T>::vector;
using fps = FormalPowerSeries;
//重要なところは某のほぼパクリ.
fps operator++(){*this += 1; return *this;}
fps operator--(){*this -= 1; return *this;}
fps operator++(int){*this += 1; return *this;}
fps operator--(int){*this -= 1; return *this;}
fps operator+(const fps &b) const {return fps(*this)+=b;}
fps operator+(const T &b) const {return fps(*this)+=b;}
fps operator-(const fps &b) const {return fps(*this)-=b;}
fps operator-(const T &b) const {return fps(*this)-=b;}
fps operator*(const fps &b){return fps(*this)*=b;}
fps operator*(const T &b) const {return fps(*this)*=b;}
fps operator/(const fps &b) const {return fps(*this)/=b;}
fps operator%(const fps &b) const {return fps(*this)%=b;}
fps operator>>(const unsigned int b) const {return fps(*this)>>=b;}
fps operator<<(const unsigned int b) const {return fps(*this)<<=b;}
fps operator-()const{ //-1倍;
fps ret = (*this);
for(auto &v : ret) v = -v;
return ret;
}
bool operator==(const fps &b)const{
if((*this).size() != b.size()) return false;
for(int i=0; i<(*this).size(); i++) if((*this).at(i) != b.at(i)) return false;
return true;
}
bool operator!=(const fps &b)const{return !((*this)==b);}
fps &operator+=(const fps &b){ //Cix^i = (Ai+Bi)x^i. O(n).
if((*this).size() < b.size()) (*this).resize(b.size(),0);
for(int i=0; i<b.size(); i++) (*this).at(i) += b.at(i);
return *this;
}
fps &operator+=(const T &b){ //x^0の係数に+b O(1).
if((*this).size() == 0) (*this).resize(1);
(*this).at(0) += b;
return *this;
}
fps &operator-=(const fps &b){ //Cix^i = (Ai-Bi)x^i. O(n).
int n = b.size();
if((*this).size() < n) (*this).resize(n,0);
for(int i=0; i<n; i++) (*this).at(i) -= b.at(i);
return *this;
}
fps &operator-=(const T &b){ //x^0の係数に-b O(1).
if((*this).size() == 0) (*this).resize(1);
(*this).at(0) -= b;
return *this;
}
fps &operator*=(const fps &b){ //C[i+k]x^(i+k) = Aix^i+Bkx^k. O(nlogn).
vector<T> re;
if(isNTTfriendly(mint::getmod())) re = convolution((*this),b); //NTT-friendlyならok 現在は4種以外認めない.
else re = convolution_llmod((*this),b);
(*this).resize(re.size());
for(int i=0; i<re.size(); i++) (*this).at(i) = re.at(i);
return *this;
}
fps &operator*=(const T &b){ //x^iの係数に*b O(n).
for(auto &v : (*this)) v *= b;
return *this;
}
fps &operator/=(const T &b){ //x^iの係数に/b O(logmod+n).
T mul = b.inv();
for(auto &v : (*this)) v *= mul;
return *this;
}
fps &operator>>=(const unsigned int &b){//b<0は対象外. 先頭b項を削除. O(n)
if((*this).size() <= b) (*this).clear();
else (*this).erase((*this).begin(),(*this).begin()+b);
return *this;
}
fps &operator<<=(const unsigned int &b){//b<0は対象外. 先頭b項に0を挿入. O(n)
(*this).insert((*this).begin(),b,0);
return *this;
}
fps &operator%=(const fps &b){ //多項式の余り. O(nlogn)
(*this) -= (*this)/b*b; del0();
return (*this);
}
fps &operator/=(const fps &b){ //多項式としての除算 O(nlogn).
assert(b.size() > 0); //分母の末尾0は駄目.
T check = b.back(); assert(check != 0);
del0(); //分子の末尾0は消して許容.
if((*this).size() < b.size()){
(*this).clear();
return *this;
}
int n = (*this).size()-b.size()+1;
if(b.size() <= 64){ //愚直.
fps G(b);
assert(G.size() > 0);
T div = G.back().inv();
for (auto &v : G) v *= div;
int deg = (*this).size()-G.size()+1;
fps Q(deg);
for(int i=deg-1; i>=0; i--){
Q[i] = (*this).at(i+G.size()-1);
for(int k=0; k<G.size(); k++) (*this).at(i+k) -= Q.at(i)*G.at(k);
}
(*this) = Q*div; (*this).resize(n,0);
return *this;
}
//rev(f)/rev(g)≡rev(ret)(mod x^n)らしい わお.
return (*this) = ((*this).rev().prefix(n) * b.rev().inv(n)).prefix(n).rev();
}
fps multi_sparse(const fps &b)const{ //非0が少ない時の掛け算 愚直 O(n*|非0|+m).
int n = (*this).size(),m = b.size();
vector<pair<int,T>> P;
for(int i=0; i<m; i++) if(b.at(i) != 0) P.push_back({i,b.at(i)});
fps ret(n+m-1);
for(int i=0; i<n; i++) for(auto [k,v] : P) ret.at(i+k) += (*this).at(i)*v;
return ret;
};
fps inv_sparse(int deg=-1)const{ //非0が少ない時の1/fを返す O(deg*|非0|+m+logmod).
int n = (*this).size();
if(deg == -1) deg = n;
assert((*this).at(0) != 0);
T div = 1;
vector<pair<int,T>> P;
if((*this).at(0) != 1) div = T((*this).at(0)).inv();
for(int i=1; i<n; i++) if((*this).at(i) != 0) P.emplace_back(pair{i,(*this).at(i)*div});
fps ret(deg); ret.at(0) = 1;
for(int i=1; i<deg; i++) for(auto [k,v] : P) if(i >= k) ret.at(i) -= v*ret.at(i-k); //-xが+ret[i-1]に対応.
if(div != 1) for(auto &v : ret) v *= div;
return ret;
}
fps inv_sparse(const fps &b,int deg = -1)const{ //f/gを返す 1/fでは分母だがこれは分子に注意.
int n = (*this).size(),m = b.size();
if(deg == -1) deg = n;
assert(b.at(0) != 0);
T div = 1;
vector<pair<int,T>> P;
if(b.at(0) != 1) div = T(b.at(0)).inv();
for(int i=1; i<m; i++) if(b.at(i) != 0) P.emplace_back(pair{i,b.at(i)*div});
fps ret = (*this).prefix(deg);
for(int i=1; i<deg; i++) for(auto [k,v] : P) if(i >= k) ret.at(i) -= v*ret.at(i-k);
if(div != 1) for(auto &v : ret) v *= div;
return ret;
}
fps log_sparse(int deg = -1){ //log(f)を返す O(N*非0).
//logf = ∫(f'/f) inv,1/f*(f')がO(N*非0) 他はO(N).
assert((*this).size()&&(*this).at(0)==1);
if(deg == -1) deg = (*this).size();
fps ret = (*this).diff();
ret = ((*this).inv_sparse(deg)).multi_sparse(ret);
return ret.inte().prefix(deg);
}
fps exp_sparse(int deg = -1)const{ //exp(f)を返す O(N*非0).
//(expf)'=(f')*exp(f)より低次から決まる.
//[x^0]expf=1より左辺のx^0の係数が求まる->expfのx^1の係数が求まる->...
if(deg == -1) deg = (*this).size();
fps ret(deg);
if((*this).size() == 0){
if(deg > 0) ret.at(0) = 1;
return ret;
}
assert((*this).at(0) == 0);
if(deg == 1) return fps{1};
ret.at(0) = 1; ret.at(1) = 1;
const long long mod = mint::getmod();
for(int i=2; i<deg; i++) ret.at(i) = (-ret.at(mod%i)*(mod/i));
vector<pair<int,T>> P;
for(int i=1; i<(*this).size(); i++) if((*this).at(i) != 0) P.emplace_back(pair{i-1,(*this).at(i)*i});
for(int i=0; i<deg-1; i++){
T now = 0;
for(auto [k,v] : P){
if(i < k) break;
now += ret.at(i-k)*v;
}
ret.at(i+1) *= now;
}
return ret;
}
fps pow_sparse(long long K,int deg = -1)const{ //f^Kを返す O(N*非0).
//f^K = Fとする fF'= K*F*f'を使う.
//[x^0]f=1に因数分解 (ax^i)^Kは別で処理.
//n次はΣ[i=0~n]fi*F'[n-i]=K*Σ[i=1~n+1]F[n+1-i]*i*fi.
//左辺のi=n以外移項 f0=1より F'n=K*Σ[i=1~n+1]F[n+1-i]*i*fi-Σ[i=1~n]fi*(n+1-i)*F[n+1-i].
//Fのn次まで分かっていればF'nが求まりFn+1も求まる F0=1からスタート.
int n = (*this).size();
if(deg == -1) deg = (*this).size();
if(K == 0 || deg == 0){
fps ret(deg);
if(deg > 0) ret.at(0) = 1;
return ret;
}
for(int t=0; t<n; t++){
if((*this).at(t) != 0){
T div = T(1)/(*this).at(t);
vector<pair<int,T>> P;
for(int i=t+1; i<n; i++) if((*this).at(i) != 0) P.emplace_back(pair{i-t,(*this).at(i)*div});
fps ret(deg); ret.at(0) = 1;
if(deg > 1) ret.at(1) = 1;
const long long mod = mint::getmod();
for(int i=2; i<deg; i++) ret.at(i) = (-ret.at(mod%i)*(mod/i));
T mulK = K%mod;
for(n=0; n<deg-1; n++){ //ここでnの役割が変わる注意.
T now = 0;
for(auto [i,v] : P){
if(i > n+1) break;
if(i > 0 && i<=n+1) now += mulK*ret.at(n+1-i)*i*v;
if(i > 0 && i <= n) now -= v*(n+1-i)*ret.at(n+1-i);
}
ret.at(n+1) *= now;
}
ret *= T((*this).at(t)).pow(K);
return (ret<<(t*K)).prefix(deg);
}
if(K >= deg || (t+1)*K >= deg) break;
}
return fps(deg,0);
}
fps diff()const{ //微分 nx^(n-1) = (x^n)' O(n).
int n = (*this).size();
if(n <= 1) return {};
fps ret(n-1);
T multi = 1;
for(int i=1; i<n; i++) ret.at(i-1) = (*this).at(i)*multi,multi++;
return ret;
}
fps inte()const{ //積分. 1/(n+1)x^(n+1) = ∫x^n dx O(n).
int n = (*this).size();
fps ret(n+1);
ret.at(0) = 0;
if(n == 0) return ret;
ret.at(1) = 1;
const long long mod = mint::getmod();
for(int i=2; i<=n; i++) ret.at(i) = (-ret.at(mod%i)*(mod/i)); //ここでret[i]=1/iになる.
for(int i=0; i<n; i++) ret.at(i+1) *= (*this).at(i);
return ret;
}
fps inv(int deg=-1)const{ //f*g=1 mod x^degとなるgを求める O(nlogn).
if(isNTTfriendly(mint::getmod())){
//g.pre(2m)<- (2g.pre(m)-f*g.pre(m)*g.pre(m))mod x^2mとする.
//fgm≡1 mod x^mからfg2m≡1 mod x^2mが求まる ダブリング.
//g2m<- gm-((fgm-1)*gm)を求める.
if((*this).size() <= 100) return inv_sparse(deg);
assert((*this).at(0) != 0);
if(deg == -1) deg = (*this).size();
fps ret(deg);
ret.at(0) = T(1)/(*this).at(0);
for(int i=1; i<deg; i<<=1){ //NTT-friendlyじゃないと駄目らしい.
fps f(2*i),g(2*i);
int n = min(2*i,(int)(*this).size());
for(int k=0; k<n; k++) f.at(k) = (*this).at(k);
for(int k=0; k<i; k++) g.at(k) = ret.at(k);
NTT(f),NTT(g);
for(int k=0; k<2*i; k++) f.at(k) *= g.at(k); //(fgm-1)を計算.
INTT(f);
for(int k=0; k<i; k++) f.at(k) = 0; //[m,2m)の項だけにする([0,m)は一致してない).
NTT(f);
for(int k=0; k<2*i; k++) f.at(k) *= g.at(k); //(fgm-1)*gmを計算.
INTT(f);
n = min(2*i,deg);
for(int k=i; k<n; k++) ret.at(k) = -f.at(k); //-(fgm^2-gm)が入る.
}
return ret; //ね、簡単でしょ？.
}
else{
//g.pre(2m)<- (2g.pre(m)-f*g.pre(m)*g.pre(m))mod x^2mとする.
//fgm≡1 mod x^mからfg2m≡1 mod x^2mが求まる ダブリング.
//こっちは愚直にやる NTT-friendlyじゃないならllmodのconvolutionに変更しないと使えない.
if((*this).size() <= 200) return inv_sparse(deg);
assert((*this).at(0) != 0);
if(deg == -1) deg = (*this).size();
fps ret(1); ret.at(0) = T(1)/(*this).at(0);
for(int i=1; i<deg; i<<=1) ret = (ret+ret-ret*ret*((*this).prefix(i<<1))).prefix(i<<1);
return ret.prefix(deg);
}
}
fps log(int deg=-1)const{ //logfを求める O(nlogn).
//log(1-f) = -Σ[n=1~∞](f^n/n)と定義する [x^0]f=1&n<modが条件.
//(logf)'=f'/f,log(fg)=logf+loggが成り立つ.
assert((*this).size()&&(*this).at(0)==1);
if(deg == -1) deg = (*this).size();
return ((*this).diff()*(*this).inv(deg)).prefix(deg-1).inte(); //∫f'/fから求める.
}
fps exp(int deg=-1)const{ //expfを求める O(nlogn).
if(isNTTfriendly(mint::getmod())){
//expf=Σ[n=0~∞]f^n/n!と定める [x^0]f=0,n<modが条件.
//(expf)'= f'expf,exp(f+g)=expf*expg,log(expf)=fを満たす (各々条件は忘れずに).
//ニュートン法で求める g2m<-gm*(1-log(gm)+f) mod x^2nに更新 納得してない.
assert((*this).size() == 0 || (*this)[0] == mint(0));
if (deg == -1) deg = (*this).size();
vector<T> divi; //invと衝突回避用 mintでiの逆元.
const long long mod = mint::getmod();
divi.resize(deg*2); divi.at(1) = 1;
for(int i=2; i<deg*2; i++) divi.at(i) = ((-divi.at(mod%i)))*(mod/i);
auto integral = [&](fps &f) -> void { //inplaceで積分.
int n = f.size();
f.insert(f.begin(),0);
for(int i=1; i<=n; i++) f.at(i) *= divi.at(i);
};
auto differential = [&](fps &f) -> void { //inplaceで微分.
if(f.size() == 0) return;
f.erase(f.begin());
T multi = 0;
for(int i=0; i<f.size(); i++) f.at(i) *= ++multi;
};
fps f({1}),g({1}),z1,z2({1,1}); //何やってるか本当に意味わからずコメント書けない 後で確認.
if((*this).size() > 1) f.push_back((*this).at(1));
else f.push_back(0);
for(int m=2; m<deg; m<<=1){
auto ff = f;
ff.resize(2*m);
NTT(ff); z1 = z2;
fps z(m);
for(int i=0; i<m; i++) z.at(i) = ff.at(i)*z1.at(i);
INTT(z);
for(int i=0; i<m/2; i++) z.at(i) = 0;
NTT(z);
for(int i=0; i<m; i++) z.at(i) *= -z1.at(i);
INTT(z);
for(int i=m/2; i<m; i++) g.emplace_back(z.at(i));
z2 = g;
z2.resize(2*m);
NTT(z2);
fps h = (*this).prefix(m);
differential(h);
h.emplace_back(T(0));
NTT(h);
for(int i=0; i<m; i++) h.at(i) *= ff.at(i);
INTT(h);
h -= f.diff();
h.resize(2*m);
for(int i=0; i<m-1; i++) h.at(m+i) = h.at(i),h.at(i) = 0;
NTT(h);
for(int i=0; i<2*m; i++) h.at(i) *= z2.at(i);
INTT(h);
h.pop_back();
integral(h);
int n = min((int)(*this).size(),2*m);
for(int i=m; i<n; i++) h.at(i) += (*this).at(i);
for(int i=0; i<m; i++) h.at(i) = 0;
NTT(h);
for(int i=0; i<2*m; i++) h.at(i) *= ff.at(i);
INTT(h);
for(int i=m; i<2*m; i++) f.emplace_back(h.at(i));
}
return f.prefix(deg);
}
else{
//NTT-friendlyじゃないとK=10^5で1sec以上かかる 畳み込みが遅い.
assert((*this).size() == 0 || (*this).at(0) == 0);
if(deg == -1) deg = (*this).size();
fps ret(1); ret.at(0) = 1;
for(int i=1; i<deg; i<<=1){
//ニュートン法 g2m<-gm*(1-log(gm)+f) mod x^2n 再掲.
ret = (ret*((*this).prefix(2*i)+T(1)-ret.log(2*i))).prefix(2*i); //logの引数普段と違う.
}
return ret.prefix(deg);
}
}
fps pow(long long K,int deg=-1)const{ //K乗を返すO(nlogn) mod10^9+7で3番目引数false.
//f^k = exp(klog(f))を使う.
//logfが計算できるように調整する.
int n = (*this).size();
if(deg == -1) deg = n;
if(K == 0){ //0乗はx^0だけ係数1.
fps ret(deg);
if(deg > 0) ret.at(0) = 1;
return ret;
}
for(int i=0; i<n; i++){
if((*this).at(i) != 0){ //0じゃなかったらOK.
const long long mod = mint::getmod();
T div = T(1)/(*this).at(i); //*([x^i]f)^Kと *x^(i*k)の分は後回し.
fps ret = ((((*this)*div)>>i).log(deg)*(K%mod)).exp(deg);
ret *= T((*this).at(i)).pow(K); //[x^i]f^Kの分.
ret = (ret<<(i*K)).prefix(deg); //*x^(i*k)の分.
return ret;
}
if(K >= deg || (i+1)*K >= deg) break; //((i+1)*K)乗未満は0確定 int128回避用にK>=deg(degがllはやばい).
}
return fps(deg,0); //fの係数全て0なら係数全て0.
}
fps prefix(int siz)const{ //先頭siz項を返す なかったら0埋め. O(siz).
fps ret((*this).begin(),(*this).begin()+min((int)(*this).size(),siz));
if(ret.size() < siz) ret.resize(siz,0);
return ret;
}
void del0(){ //末尾の0を消す O(n).
while((*this).size() && (*this).back() == 0) (*this).pop_back();
}
fps rev()const{ //ひっくり返す O(n).
fps ret(*this);
reverse(ret.begin(),ret.end());
return ret;
}
pair<fps,fps> getQR(const fps &b)const{ //多項式の商と余りを同時に得る O(nlogn).
fps Q = (*this)/b,R = (*this)-Q*b;
R.del0();
return {Q,R};
}
fps cumulativeNtimes(int N,T b,int deg=-1){ //1/(1-bx)^Nをdeg次まで返す 指定なしはN次まで.
//負の二項定理を使う. 1/(1-x)^N=Σ[i=0~∞]((n+i-1) choose i)(bx^i);
//fps{}.cumulativeNtime()で無理やり関数を呼び出す.
assert(N <= 0); //N=0も駄目? {1}を返すべき所{0}になる.
if(deg == -1) deg = N+1;
int Limit = N+deg; //Limit 必要なサイズ fac->x! facinv->1/x! inv->1/x.
long long mod = mint::getmod(),invstart = min((int)mod-1,Limit);
vector<T> FAC(Limit+1,1); for(int i=1; i<=Limit; i++) FAC.at(i) = FAC.at(i-1)*i;
vector<T> FACinv(Limit+1); FACinv.at(invstart) = FAC.at(invstart).inv();
for(int i=invstart-1; i>=0; i--) FACinv.at(i) = FACinv.at(i+1)*(i+1);
auto nCr = [&](int n, int r) -> T {
if(n < r || r < 0 || n < 0) return 0;
return FAC.at(n)*FACinv.at(r)*FACinv.at(n-r);
};
fps ret(deg); T value = 1;
for(int i=0; i<deg; i++) ret.at(i) = nCr(N+i-1,i)*value,value *= b;
return ret;
}
fps Taylorshift(long long C)const{ //Σ[i=0~n]Ai*(x+c)^iを返す O(nlogn).
//Σ[i=0~n]x^i/i! Σ[k=0~n-i](A[i+k]*(i+k)!)*(c^k/k!)になる.
//kの部分はXi=Ai*i!,Yi=c^i/i!として.Zi=ΣX[i+k]Yk.
//これは[x^(i+n)]X*rev(Y)で求められる.
const long long mod = mint::getmod();
mint c = (C%mod+mod)%mod,pc = 1;
if(c == 0) return (*this);
int deg = (*this).size(); //deg 必要なサイズ fac->x! facinv->1/x! inv->1/x.
long long invstart = min((int)mod-1,deg);
vector<mint> fac(deg+1,1); for(int i=1; i<=deg; i++) fac.at(i) = fac.at(i-1)*i;
vector<mint> facinv(deg+1); facinv.at(invstart) = fac.at(invstart).inv();
for(int i=invstart-1; i>=0; i--) facinv.at(i) = facinv.at(i+1)*(i+1);
fps X(deg),Y(deg);
for(int i=0; i<deg; i++) X.at(i) = (*this).at(i)*fac.at(i),Y.at(deg-1-i) = pc*facinv.at(i),pc *= c;
X *= Y;
fps ret(deg);
for(int i=0; i<deg; i++) ret.at(i) = X.at(i+deg-1)*facinv.at(i);
return ret;
}
};
using fps = FormalPowerSeries<mint>;
mint BostanMori(long long N,fps P,fps Q){
P.del0(); Q.del0();
int K = Q.size();
mint ret = 0;
if(P.size() >= Q.size()){ //deg(P)>=deg(Q)の時.
auto R = P/Q;
P -= R*Q; P.del0();
if(N < R.size()) ret += R.at(N);
}
if(P.size() == 0) return ret;
if(mint::getmod()){ //mod998244353以外はNTT-friendlyじゃないと認識する.
int n = 1;
while(n < K) n <<= 1;
P.resize(2*n); Q.resize(2*n);
NTT(P),NTT(Q);
vector<mint> S(n),T(n);
vector<int> Bitrev(n); //ビットリバース.
for(int i=0; i<n; i++){
if(i&1) Bitrev.at(i) = n>>1;
Bitrev.at(i) += (Bitrev.at(i>>1)>>1);
}
fftinfo<mint> info;
mint dw = info.g.inv().pow((mint::getmod()-1)/(n<<1)),Div2 = mint(1)/2;
while(N){
mint div2 = Div2;
S.resize(n),T.resize(n);
for(int i=0; i<(n<<1); i+=2) T.at(i>>1) = Q.at(i)*Q.at(i+1); //Q(x)Q(-x)の偶数次.
if(N&1){ //P(x)Q(-x)の奇数次.
for(auto i : Bitrev){
S.at(i) = (P.at(i<<1)*Q.at((i<<1)+1)-P.at((i<<1)+1)*Q.at(i<<1))*div2;
div2 *= dw; //これ分からん.
}
}
else{ //P(x)Q(-x)の偶数次.
for(int i=0; i<(n<<1); i+=2) S.at(i>>1) = (P.at(i)*Q.at(i+1)+P.at(i+1)*Q.at(i))*div2;
}
swap(P,S),swap(Q,T);
N >>= 1;
if(N < n) break;
NTTdoubling(P),NTTdoubling(Q);
}
INTT(P),INTT(Q);
Q = Q.inv();
for(int i=0; i<=N; i++) ret += P.at(i)*Q.at(N-i); //ret+=[x^N]P/Q
return ret;
}
else{ //P(x)/Q(x)=P(x)Q(-x)/Q(x)Q(-x) 分母の奇数次は全部0になる.
P.resize(K-1);
while(N){
fps Q2 = Q;
for(int i=1; i<Q2.size(); i+=2) Q2.at(i) = -Q2.at(i);
P *= Q2,Q *= Q2;
for(int i=0; i<Q.size(); i+=2) Q.at(i>>1) = Q.at(i); //偶数次しかないので次数/2をする.
Q.resize((Q.size()+1)>>1);
if(N&1){ //Nthが奇数の場合は分子の偶数次は要らない (分母が偶数次しかない).
for(int i=1; i<P.size(); i+=2) P.at(i>>1) = P.at(i);
P.resize(P.size()>>1);
}
else{ //Nthが偶数.
for(int i=0; i<P.size(); i+=2) P.at(i>>1) = P.at(i);
P.resize((P.size()+1)>>1);
}
N >>= 1;
}
return ret+P.at(0);
}
}
mint NthLinearlyRecurrent(long long N,const fps &A,fps C){ //Ai(i>=K)=Σ[j=1~K]Cj*A[i-j]のN番目を求める.
//P = Q*A->[x^N]P/Qで求める O(KlogKlogN).
//Q = 1-Σ[i=1~K]Cix^i. PはK次未満の項しかない.
assert(C.size() && C.at(0) != 0);
if(N < A.size()) return A.at(N); //元々Nthがある場合.
assert(A.size() >= C.size()); //A[K-1]までは与えられている必要がある.
C.insert(C.begin(),mint(-1));
for(auto &v : C) v = -v;
fps P = A.prefix((int)C.size()-1)*C;
P.resize(C.size()-1);
return BostanMori(N,P,C);
}
fps BarlekampMassey(const fps &A){ //線形漸化式の初めのn項の特性方程式を返す d次ならO(d^2).
//d次->2*d項があれば十分 ΣCix^i=0のCiを返す C0=1.
int M = A.size();
mint y = 1; //1つ前のxの値.
fps C,B;//Cはret Bは1つ前のC.
C.reserve(M+1),B.reserve(M+1);
C.emplace_back(mint(1)),B.emplace_back(mint(1));
for(int i=1; i<=M; i++){
int lc = C.size(),lb = B.size();
mint x = 0;
for(int k=0; k<lc; k++) x += C.at(k)*A.at(i-lc+k); //revしている?.
B.emplace_back(mint(0)); lb++;
if(x == 0) continue;
mint Multi = x/y;
if(lc < lb){ //C<-C-x/y*x^m*B B.emplace_back(0)でx^mを担当?.
auto memo = C;
C <<= lb-lc;
for(int k=0; k<lb; k++) C.at(k) -= Multi*B.at(k); //O(d^2)の「掛け算」が重い モンゴメれば2倍速.
B = memo; y = x;
}
else for(int k=0; k<lb; k++) C.at(lc-1-k) -= Multi*B.at(lb-1-k);
}
reverse(C.begin(),C.end());//revで考えていたので元に戻す.
return C; //何やってるか分からないシリーズ.
}
mint BMBM(long long N,const fps &A){ //線形漸化式の初めのn項からN項目を求める d次漸化式ならO(d^2+dlogdlogN).
if(N < 0) return 0;
fps C = BarlekampMassey(A);
fps P = A.prefix((int)C.size()-1)*C;
P.resize(C.size()-1);
return BostanMori(N,P,C);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long K,L,R; cin >> K >> L >> R;
const long long mod = 998244353;
int n = 5000;
fps A(n);
A.at(0) = 1;
for(int i=1; i<n; i++) A.at(i) = A.at(i-1)*K+mint(i-1).pow(K)+mint(K).pow(i-1);
for(int i=1; i<n; ++i) A.at(i) += A.at(i-1);
cout << (BMBM(R,A)-BMBM(L-1,A)).v << endl;
return 0;
{
auto touhi = [&](mint a,mint r,long long n) -> mint {
if(r == 1) return a*(n%mod);
return a*(mint(1)-r.pow(n))/(mint(1)-r);
};
auto f = [&](long long x) -> mint {
if(x < 0) return 0;
if(x == 0) return 1;
mint ret = 0,add = 0;
ret += touhi(1,K,x+1);
};
cout << (f(R)-f(L-1)).v << endl;
}
}