#778142 (C++17) No.2007 Arbitrary Mod (Easy)

提出ソース

結果

問題	No.2007 Arbitrary Mod (Easy)
ユーザー	bin101
提出日時	2022-07-15 21:22:06
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	11,143 bytes
コンパイル時間	1,328 ms
コンパイル使用メモリ	134,720 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-27 16:42:35
合計ジャッジ時間	4,002 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"
using namespace std;
using ll=long long int;
//using Int=__int128;
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> constexpr int bitUP(T x,int a){return (x>>a)&1;}
//→　↓　←　↑ 
int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0};
//右上から時計回り
//int dh[8]={-1,0,1,1,1,0,-1,-1}, dw[8]={1,1,1,0,-1,-1,-1,0};
long double EPS = 1e-6;
long double PI = acos(-1);
const ll INF=(1LL<<62);
const int MAX=(1<<30);
//constexpr ll MOD=1000000000+7;
constexpr ll MOD=998244353;


inline void bin101(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
}

using pii=pair<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;

using Graph=vector<vector<int>>;

template<typename T >
struct edge {
	int to;
	T cost;
	edge()=default;
	edge(int to, T cost) : to(to), cost(cost) {}

};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;

template<typename T>
void CinGraph(int M,WeightGraph<T> &g,bool directed=false,bool index1=true){
    while(M--){
        int s,t;
        T cost;
        cin>>s>>t>>cost;
        if(index1) s--,t--;
        g[s].emplace_back(t,cost);
        if(not directed) g[t].emplace_back(s,cost);
    }
}

void CinGraph(int M,Graph &g,bool directed=false,bool index1=true){
    while(M--){
        int s,t;
        cin>>s>>t;
        if(index1) s--,t--;
        g[s].push_back(t);
        if(not directed) g[t].push_back(s);
    }
}


//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<T> &v) {
    for(size_t i=0;i<v.size();i++) is>>v[i];
	return is;
}
 
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        is>>v[i];
    }
    return is;
}
//vector cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<T> &v) {
    bool sp=true;
    if(string(typeid(T).name())=="c") sp=false;
    for(size_t i=0;i<v.size();i++){
        if(i and sp) os<<" ";
        os<<v[i];
    }
    return os;
}
//vector<vector> cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {
    for(size_t i=0;i<v.size();i++){
        os<<v[i];
        if(i+1!=v.size()) os<<"\n";
    }
    return os;
}

//Graph out
template<typename T>
inline ostream &operator<<(ostream &os,const Graph &g) {
    for(size_t i=0;i<g.size();i++){
        for(int to:g[i]){
            os<<i<<"->"<<to<<" ";
        }
        os<<endl;
    }
    return os;
}

//WeightGraph out
template<typename T>
inline ostream &operator<<(ostream &os,const WeightGraph<T> &g) {
    for(size_t i=0;i<g.size();i++){
        for(auto e:g[i]){
            os<<i<<"->"<<e.to<<"("<<e.cost<<") ";
        }
        os<<endl;
    }
    return os;
}


//要素数n 初期値x
template<typename T>
inline vector<T> vmake(size_t n,T x){
	return vector<T>(n,x);
}

//a,b,c,x data[a][b][c] 初期値x
template<typename... Args>
auto vmake(size_t n,Args... args){
	auto v=vmake(args...);
	return vector<decltype(v)>(n,move(v));
}
template<typename V,typename T>
void fill(V &v,const T value){
    v=value;
}

template<typename V,typename T>
void fill(vector<V> &vec,const T value){
    for(auto &v:vec) fill(v,value);
}

//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
	os<<p.first<<" "<<p.second;
	return os;
}
 
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
	is>>p.first>>p.second;
	return is;
}
 
//ソート
template<typename T>
inline void vsort(vector<T> &v){
    sort(v.begin(),v.end());
}
 
//逆順ソート
template<typename T>
inline void rvsort(vector<T> &v){
	sort(v.rbegin(),v.rend());
}

//1ビットの数を返す
inline int popcount(int x){
	return __builtin_popcount(x);
}
//1ビットの数を返す
inline int popcount(ll x){
	return __builtin_popcountll(x);
}
template<typename T>
inline void Compress(vector<T> &C){
    sort(C.begin(),C.end());
    C.erase(unique(C.begin(),C.end()),C.end());
}
template<typename T>
inline int lower_idx(const vector<T> &C,T value){
    return lower_bound(C.begin(),C.end(),value)-C.begin();
}
template<typename T>
inline int upper_idx(const vector<T> &C,T value){
    return upper_bound(C.begin(),C.end(),value)-C.begin();
}
//時計回りに90度回転
template<typename T>
inline void rotate90(vector<vector<T>> &C){
    vector<vector<T>> D(C[0].size(),vector<T>(C.size()));
    for(int h=0;h<C.size();h++){
        for(int w=0;w<C[h].size();w++){
            D[w][C.size()-1-h]=C[h][w];
        }
    }
    C=D;
}

//0indexを想定
bool OutGrid(ll h,ll w,ll H,ll W){
    return (h>=H or w>=W or h<0 or w<0);
}

void NO(){
    cout<<"NO"<<"\n";
}
void YES(){
    cout<<"YES"<<"\n";
}
void No(){
    cout<<"No"<<"\n";
}
void Yes(){
    cout<<"Yes"<<"\n";
}
namespace overflow{
    template<typename T>
    T max(){
        return numeric_limits<T>::max();
    }
    template<typename T>
    T ADD(T a,T b){
        T res;
        return __builtin_add_overflow(a,b,&res)?max<T>():res;
    }
    template<typename T>
    T MUL(T a,T b){
        T res;
        return __builtin_mul_overflow(a,b,&res)?max<T>():res;
    }
};
using namespace overflow;
struct mint{
    using u64=uint_fast64_t;
    u64 a;
    constexpr mint() :a(0){}
    constexpr mint(ll x) :a((x>=0)?(x%MOD):(x%MOD+MOD) ) {}

    inline constexpr mint operator+(const mint rhs)const noexcept{
        return mint(*this)+=rhs;
    }
    inline constexpr mint operator-(const mint rhs)const noexcept{
        return mint(*this)-=rhs;
    }
    inline constexpr mint operator*(const mint rhs)const noexcept{
        return mint(*this)*=rhs;
    }
    inline constexpr mint operator/(const mint rhs)const noexcept{
        return mint(*this)/=rhs;
    }
    inline constexpr mint operator+(const ll rhs) const noexcept{
        return mint(*this)+=mint(rhs);
    }
    inline constexpr mint operator-(const ll rhs)const noexcept{
        return mint(*this)-=mint(rhs);
    }
    inline constexpr mint operator*(const ll rhs)const noexcept{
        return mint(*this)*=mint(rhs);
    }
    inline constexpr mint operator/(const ll rhs)const noexcept{
        return mint(*this)/=mint(rhs);
    }

    inline constexpr mint &operator+=(const mint rhs)noexcept{
        a+=rhs.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    inline constexpr mint &operator-=(const mint rhs)noexcept{
        if(rhs.a>a) a+=MOD;
        a-=rhs.a;
        return *this;
    }
    inline constexpr mint &operator*=(const mint rhs)noexcept{
        a=(a*rhs.a)%MOD;
        return *this;
    }
    inline constexpr mint &operator/=(mint rhs)noexcept{
        a=(a*rhs.inverse().a)%MOD;
        return *this;
    }
    inline constexpr mint &operator+=(const ll rhs)noexcept{
        return *this+=mint(rhs);
    }
    inline constexpr mint &operator-=(const ll rhs)noexcept{
        return *this-=mint(rhs);
    }
    inline constexpr mint &operator*=(const ll rhs)noexcept{
        return *this*=mint(rhs);
    }
    inline constexpr mint &operator/=(const ll rhs)noexcept{
        return *this/=mint(rhs);
    }

    inline constexpr mint operator=(const ll x)noexcept{
        a=(x>=0)?(x%MOD):(x%MOD+MOD);
        return *this;
    }

    inline constexpr bool operator==(const mint p)const noexcept{
        return a==p.a;
    }

    inline constexpr bool operator!=(const mint p)const noexcept{
        return a!=p.a;
    }

    inline constexpr mint pow(ll N) const noexcept{
        mint ans(1LL),p(a);
        while(N>0){
            if(bitUP(N,0)){
                ans*=p;
            }
            p*=p;
            N>>=1;
        }
        return ans;
    }
    inline constexpr mint inverse() const noexcept{
        return pow(MOD-2);
    }

};
inline constexpr mint operator+(const ll &a,const mint &b)noexcept{
    return mint(a)+=b;
}
inline constexpr mint operator-(const ll &a,const mint &b)noexcept{
    return mint(a)-=b;
}
inline constexpr mint operator*(const ll &a,const mint &b)noexcept{
    return mint(a)*=b;
}
inline constexpr mint operator/(const ll &a,const mint &b)noexcept{
    return mint(a)/=b;
}
//cout
inline ostream &operator<<(ostream &os,const mint &p) {
    return os<<p.a;
}

//cin
inline istream &operator>>(istream &is,mint &p) {
    ll t;
    is>>t;
    p=t;
    return is;
}

struct Binominal{
    vector<mint> fac,finv,inv; //fac[n]:n! finv:(n!)の逆元
    int sz;
    Binominal(int n=10) :sz(1){
        if(n<=0) n=10;
        init(n);
    }
    inline void init(int n){
        fac.resize(n+1,1);
        finv.resize(n+1,1);
        inv.resize(n+1,1);
        for(int i=sz+1;i<=n;i++){
            fac[i]=fac[i-1]*i;
            inv[i]=MOD-inv[MOD%i]*(MOD/i);
            finv[i]=finv[i-1]*inv[i];
        }
        sz=n;
    }
    //nCk(n,k<=N) をO(1)で求める
    inline mint com(int n,int k){
        if(n<k) return mint(0);
        if(n<0 || k<0) return mint(0);
        if(n>sz) init(n);
        return fac[n]*finv[k]*finv[n-k];
    }
    //nCk(k<=N) をO(k)　で求める 
    inline mint rcom(ll n,int k){
        if(n<0 || k<0 || n<k) return mint(0);
        if(k>sz) init(k);
        mint ret(1);
        for(int i=0;i<k;i++){
            ret*=n-i;
        }
        ret*=finv[k];
        return ret;
    }

    //重複組み合わせ n種類のものから重複を許してk個を選ぶ
    //〇がn個,|がk個
    inline mint h(int n,int k){
        return com(n+k-1,k);
    }
    //順列の公式
    inline mint P(int n,int k){
        if(n<k) return 0;
        if(n>sz) init(n);
        return fac[n]*finv[n-k];
    }

};
vector<int> Subset(int S,bool zero=false,bool full=false){
    vector<int> ret;
    int now=(S-1)&S;
    if(full and S){
        ret.push_back(S);
    }
    do{
        ret.push_back(now);
        now=(now-1)&S;
    }while(now!=0);
    if(zero){
        ret.push_back(0);
    }
    return ret;
}
template<typename T>
T SUM(const vector<T> &v,int s,int t){
    chmax(s,0);
    chmin(t,int(v.size())-1);
    if(s>t) return 0;
    if(s==0) return v[t];
    else return v[t]-v[s-1];
}
template<typename T>
void buildSUM(vector<T> &v){
    for(size_t i=1;i<v.size();i++){
        v[i]+=v[i-1];
    }
    return;
}

void solve(){
    mint a;
    ll n;
    cin>>a>>n;
    a=a.pow(n);
    cout<<MOD<<endl;
    cout<<a<<endl;
}

int main(){
    bin101();
    int T=1;
    //cin>>T;
    while(T--) solve();
}

yukicoder

結果

テストケース

ソースコード