#830706 (C++17) No.2176 LRM Question 1

提出ソース
結果

問題	No.2176 LRM Question 1
ユーザー	hari64
提出日時	2023-01-06 21:34:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	17 ms / 2,000 ms
コード長	14,295 bytes
コンパイル時間	2,521 ms
コンパイル使用メモリ	225,000 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-05-07 21:04:35
合計ジャッジ時間	3,323 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,812 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,948 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	17 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	1 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	1 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	1 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifndef hari64
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#include "viewer.hpp"
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif  // clang-format off
using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;
template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;}  // clang-format on

// clang-format off
namespace internal{template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T,__int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;
constexpr long long safe_mod(long long x,long long m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m):_m(m),im((unsigned long long)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned long long z=a;z*=b;unsigned long long x=(unsigned long long)(((unsigned __int128)(z)*im)>>64);unsigned int v=(unsigned int)(z-x*_m);if(_m<=v)v+=_m;return v;}};
constexpr long long pow_mod_constexpr(long long x,long long n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned long long r=1;unsigned long long y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr pair<long long,long long>inv_gcd(long long a,long long b){a=safe_mod(a,b);if(a==0)return{b,0};long long s=b,t=a;long long m0=0,m1=1;while(t){long long u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long long d=n-1;while(d%2==0)d/=2;constexpr long long bases[3]={2,7,61};for(long long a:bases){long long t=d;long long y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}template<int n>constexpr bool is_prime=is_prime_constexpr(n);} // namespace internal
template<int m>struct static_modint{using mint=static_modint;static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){long long x=(long long)(v%(long long)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}
mint&operator*=(const mint&rhs){unsigned long long z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&is,mint&rhs){long long v;is>>v;v%=(long long)(umod());if(v<0)v+=umod();;rhs._v=(unsigned int)v;return is;}static constexpr bool prime=internal::is_prime<m>;private:unsigned int _v;static constexpr unsigned int umod(){return m;}};
constexpr int MOD = 998244353;using mint=static_modint<MOD>;vector<mint>mint_factorial={mint(1)};/*n>1e8 ⇒ fast_modfact(deprecated)*/mint modfact(int n){assert(n<=100000000);if(int(mint_factorial.size())<=n){for(int i=mint_factorial.size();i<=n;i++){mint next=mint_factorial.back()*i;mint_factorial.push_back(next);}}return mint_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::mod();if(a.val()==1)return a;if(a.pow((p-1)>>1).val()!=1)return -1;mint b=1,one=1;while(b.pow((p-1)>>1).val()==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=a.pow((m-1)>>1);mint y=a*x*x;x*=a;mint z=b.pow(m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=z.pow(1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*(modfact(k)).inv()*modfact(n-k).inv();}
/*min x s.t. a^x ≡ b (mod M) or -1*/int modlog(mint a,mint b){if(gcd(a.mod(),a.val())!=1){cout<<"\033[1;31mCAUTION: m must be coprime to a.\033[0m"<<endl;assert(false);}long long m=mint::mod();long long sq=round(sqrt(m))+1;unordered_map<long long,long long>ap;mint re=a;for(long long r=1;r<sq;r++){if(ap.find(re.val())==ap.end())ap[re.val()]=r;re*=a;}mint A=a.inv().pow(sq);re=b;for(mint q=0;q.val()<sq;q++){if(re==1&&q!=0)return(q*sq).val();if(ap.find(re.val())!=ap.end())return(q*sq+ap[re.val()]).val();re*=A;}return-1;};
// clang-format on

/*math library*/  // clang-format off
// dynamic modint
template<int id>struct dynamic_modint{using mint=dynamic_modint;static int mod(){return(int)(bt.umod());}
static mint raw(int v){mint x;x._v=v;return x;}dynamic_modint():_v(0){}
template<class T,internal::is_signed_int_t<T>* =nullptr>dynamic_modint(T v){long long x=(v%(long long)(mod()));if(x<0)x+=mod();_v=(unsigned int)(x);}
template<class T,internal::is_unsigned_int_t<T>* =nullptr>dynamic_modint(T v){_v=(unsigned int)(v%mod());}
unsigned int val()const{return _v;}
static void set_mod(int m){assert(1<=m);bt=internal::barrett(m);}mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v+=mod()-rhs._v;if(_v>=umod())_v-=umod();return*this;}
mint&operator*=(const mint&rhs){_v=bt.mul(_v,rhs._v);return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{auto eg=internal::inv_gcd(_v,mod());assert(eg.first==1);return eg.second;}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&os,mint&rhs){long long v;os>>v;v%=(long long)(mod());if(v<0)v+=mod();;rhs._v=(unsigned int)v;return os;}
private:unsigned int _v;static internal::barrett bt;static unsigned int umod(){return bt.umod();}};template<int id>internal::barrett dynamic_modint<id>::bt(998244353);
using dmint=dynamic_modint<-1>; // in main(), write "dmint::set_mod(mod);"
// x ^ n (mod m)
long long pow_mod(long long x,long long n,int m){assert(0<=n&&1<=m);if(m==1)return 0;internal::barrett bt((unsigned int)(m));unsigned int r=1,y=(unsigned int)(internal::safe_mod(x,m));while(n){if(n&1)r=bt.mul(r,y);y=bt.mul(y,y);n>>=1;}return r;}
// y s.t. xy = 1 (mod m) && 0 <= y < m (require: gcd(x, m) == 1)
long long inv_mod(long long x,long long m){assert(1<=m);auto z=internal::inv_gcd(x,m);assert(z.first==1);return z.second;}
// (R,M) s.t. 0 <= R < M = lcm(m[i]) && R = x(mod M) where x = r[i] (mod m[i]) ∀i ∊ {0, ... , n - 1}
pair<long long,long long>crt(const vector<long long>&r,const vector<long long>&m){assert(r.size()==m.size());int n=int(r.size());long long r0=0,m0=1;
    for(int i=0;i<n;i++){assert(1<=m[i]);long long r1=internal::safe_mod(r[i],m[i]),m1=m[i];if(m0<m1){swap(r0,r1);swap(m0,m1);}if(m0%m1==0){if(r0%m1!=r1)return{0,0};continue;}long long g,im;tie(g,im)=internal::inv_gcd(m0,m1);long long u1=(m1/g);if((r1-r0)%g)return{0,0};long long x=(r1-r0)/g%u1*im%u1;r0+=x*m0;m0*=u1;if(r0<0)r0+=m0;}return{r0,m0};}
// Σ_{i=0}^{n-1} ⌊(a*i+b)/m⌋ (mod 2^64)
long long floor_sum(long long n,long long m,long long a,long long b){assert(0<=n&&n<(1LL<<32));assert(1<=m&&m<(1LL<<32));unsigned long long ans=0;if(a<0){unsigned long long a2=internal::safe_mod(a,m);ans-=1ULL*n*(n-1)/2*((a2-a)/m);a=a2;}if(b<0){unsigned long long b2=internal::safe_mod(b,m);ans-=1ULL*n*((b2-b)/m);b=b2;}
    unsigned long long ans2=0;while(true){if(a>=m){ans2+=n*(n-1)/2*(a/m);a%=m;}if(b>=m){ans2+=n*(b/m);b%=m;}unsigned long long y_max=a*n+b;if(y_max<(unsigned long long)m)break;n=(unsigned long long)(y_max/m);b=(unsigned long long)(y_max%m);swap(m,a);}return ans+ans2;}
// primitive root
constexpr int primitive_root_constexpr(int m){assert(internal::is_prime_constexpr(m));if(m==2)return 1;if(m==167772161)return 3;if(m==469762049)return 3;if(m==754974721)return 11;if(m==998244353)return 3;
    int divs[20]={};divs[0]=2;int cnt=1;int x=(m-1)/2;while(x%2==0)x/=2;for(int i=3;(long long)(i)*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0)x/=i;}}if(x>1)divs[cnt++]=x;for(int g=2;;g++){bool ok=true;for(int i=0;i<cnt;i++){if(internal::pow_mod_constexpr(g,(m-1)/divs[i],m)==1){ok=false;break;}}if(ok)return g;}}
template<int m>constexpr int primitive_root=primitive_root_constexpr(m);
// nCK (mod prime) (n <= 10^9) (There is room for improvement)
struct aribitary_prime_mod_combination{vector<unsigned int>fact,ifact,inv;
    // O(sz)
    aribitary_prime_mod_combination(int sz,long long mod):fact(sz+1),ifact(sz+1),inv(sz+1){assert(internal::is_prime_constexpr(mod));fact[0]=fact[1]=ifact[0]=ifact[1]=inv[1]=1;internal::barrett bt(mod);for(int i=2;i<=sz;i++){fact[i]=bt.mul(fact[i-1],i);inv[i]=MOD-bt.mul(inv[MOD%i],MOD/i);ifact[i]=bt.mul(ifact[i-1],inv[i]);}}
    // O(k) nCk = (Π_{i = n - k + 1}^{n} i) / k!
    long long nCk_smallK(long long n,long long k,long long mod){assert(n>=k);assert(n>=0&&k>=0);assert(int(ifact.size())>k);return fact[n]*ifact[k]*ifact[n-k];}
};
// nCk (mod any int) (k, n <= 5000)
vector<vector<long long>>calc_nCk_table(long long mod,int table_sz=5000){vector<vector<long long>>nCk_table(table_sz+1,vector<long long>(table_sz+1,0));nCk_table[0][0]=1;for(int i=1;i<=table_sz;++i){nCk_table[i][0]=1;for(int j=1;j<=table_sz;++j)nCk_table[i][j]=(nCk_table[i-1][j-1]+nCk_table[i-1][j])%mod;}return nCk_table;}
// https://manabitimes.jp/math/1324 (高校数学の美しい物語 Lucasの定理とその証明)
// https://w.atwiki.jp/uwicoder/pages/2118.html (uwicoder nCr mod mの求め方)
// https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf
// nCm (mod p^q) in O(log^2 n + q^4 log n log p + q^4 p log^3 p)
long long generalization_of_lucas_theorem(long long n,long long m,long long p,long long q,long long pq){if(n<0||m<0||m>n)return 0;internal::barrett bt(pq);vector<long long>fact(pq+1),ifact(pq+1);fact[0]=ifact[0]=1;for(int i=1;i<=pq;i++){if(i%p==0){fact[i]=fact[i-1];}else{fact[i]=bt.mul(fact[i-1],i);}ifact[i]=inv_mod(fact[i],pq);}
    long long z=n-m;int e0=0;for(long long u=n/p;u;u/=p)e0+=u;for(long long u=m/p;u;u/=p)e0-=u;for(long long u=z/p;u;u/=p)e0-=u;int em=0;for(long long u=n/pq;u;u/=p)em+=u;for(long long u=m/pq;u;u/=p)em-=u;for(long long u=z/pq;u;u/=p)em-=u;long long ret=1;while(n>0){ret=bt.mul(bt.mul(bt.mul(ret,fact[n%pq]),inv_mod(fact[m%pq],pq)),inv_mod(fact[z%pq],pq));n/=p;m/=p;z/=p;}ret=bt.mul(ret,pow_mod(p,e0,pq));if(!(p==2&&q>=3)&&em%2)ret=(pq-ret)%pq;return ret;}
// mod <= 10^7 (The mod doesn't have to be a prime number!) verified with python's arbitrary precision integers
long long nCk_lucas(long long n,long long k,long long mod){assert(mod<=10000000);vector<long long>rems,mods;for(int p=2;p*p<=mod;++p){if(mod%p!=0)continue;int q=0;int pq=1;while(mod%p==0)q++,mod/=p,pq*=p;rems.push_back(generalization_of_lucas_theorem(n,k,p,q,pq));mods.push_back(pq);}if(mod!=1){rems.push_back(generalization_of_lucas_theorem(n,k,mod,1,mod));mods.push_back(mod);};return crt(rems,mods).first;}
// clang-format on

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    long long L, R, M;
    cin >> L >> R >> M;

    dmint::set_mod(M);
    dmint ans = 0;
    dmint f = 1;
    dmint g = 1;
    for (int i = 1; i < L; i++) {
        f *= i;
        g *= f;
        if (f == 0) {
            break;
        }
    }
    for (int i = L; i <= R; i++) {
        f *= i;
        g *= f;
        ans += g;
        if (f == 0) {
            break;
        }
    }
    cout << ans << endl;

    return 0;
}
yukicoder

結果

テストケース

ソースコード
