#344816 (C++14) No.827 総神童数

提出ソース

結果

問題	No.827 総神童数
ユーザー	NyaanNyaan
提出日時	2019-05-03 22:38:34
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	234 ms / 2,000 ms
コード長	6,594 bytes
コンパイル時間	941 ms
コンパイル使用メモリ	102,328 KB
実行使用メモリ	16,200 KB
最終ジャッジ日時	2024-06-10 06:45:36
合計ジャッジ時間	6,218 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	3 ms 6,940 KB
testcase_09	AC	216 ms 16,200 KB
testcase_10	AC	71 ms 7,808 KB
testcase_11	AC	5 ms 6,944 KB
testcase_12	AC	31 ms 6,944 KB
testcase_13	AC	170 ms 13,636 KB
testcase_14	AC	8 ms 6,940 KB
testcase_15	AC	65 ms 7,424 KB
testcase_16	AC	167 ms 13,732 KB
testcase_17	AC	202 ms 15,660 KB
testcase_18	AC	88 ms 8,704 KB
testcase_19	AC	234 ms 16,152 KB
testcase_20	AC	159 ms 12,912 KB
testcase_21	AC	107 ms 11,064 KB
testcase_22	AC	174 ms 13,692 KB
testcase_23	AC	3 ms 6,940 KB
testcase_24	AC	200 ms 14,784 KB
testcase_25	AC	150 ms 12,160 KB
testcase_26	AC	193 ms 14,956 KB
testcase_27	AC	118 ms 11,004 KB
testcase_28	AC	125 ms 10,880 KB
testcase_29	AC	96 ms 9,472 KB
testcase_30	AC	29 ms 6,948 KB
testcase_31	AC	77 ms 8,064 KB
testcase_32	AC	74 ms 9,032 KB
testcase_33	AC	231 ms 15,872 KB
testcase_34	AC	205 ms 14,668 KB
testcase_35	AC	76 ms 8,064 KB
testcase_36	AC	106 ms 10,112 KB
testcase_37	AC	143 ms 12,032 KB
testcase_38	AC	217 ms 15,620 KB

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

ソースコード

raw source code

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define whlie while
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define inf 1001001001
#define mod 1000000007
#define FOR(i,a,b) for(int (i)=((int)a); (i)<((int)b); (i)++) // [a,b)
#define rep(i,N) FOR((i), 0, ((int)N)) // [0,N)
#define FORR(i,a,b) for(int (i)=((int)b) - 1; (i)>=((int)a); (i)--)
#define repr(i,N) FORR((i), 0, ((int)N))
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it=v.begin();it<v.end();it++)
#define vrepr(v,it) for(auto it=v.rbegin();it<v.rend();it++)
#define inx(t,...) t __VA_ARGS__; in(__VA_ARGS__)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define ind(...) double __VA_ARGS__; in(__VA_ARGS__)
#define inpii(...) pii __VA_ARGS__; in(__VA_ARGS__)
#define invi(v,...) vi v; in(v,##__VA_ARGS__)
#define invl(v,...) vl v; in(v,##__VA_ARGS__)

// デバッグ用
// dbg(...) printfと同様に使用可能 
// trc(var) (変数名)=(値)と表示
// stopif(val) 条件分が真の時に止まる
// vd(v,N) vの中身を表示

#ifdef LOCAL
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
    #define trc(...) cout << #__VA_ARGS__ << "="; dbg_out(__VA_ARGS__)
    #define stopif(val) assert( !(val) )
    #define vdbg(v,...) cout << #v << "={"; vector_debug(v , ##__VA_ARGS__)
#else
    #define dbg(...) 1
    #define trc(...) 1
    #define stopif(...) 1
    #define vdbg(...) 1
#endif

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector< vector<int> > vvi;
int gcd(int a, int b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} ll gcd(ll a, ll b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);}
int lcm(int a, int b){return (a / gcd(a,b)) * b;} ll lcm(ll a, ll b){return (a / gcd(a,b)) * b;}
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename C> inline void _cin(C &c){cin >> c;} template<typename T,typename U> inline void _cin(pair<T,U> &p){cin >> p.fi; cin >> p.se;}
template<typename C> inline void _cout(const C &c){cout << c;} template<typename T,typename U> inline void _cout(const pair<T,U> &p){cout << p.fi << ' ' << p.se;}
void in(){} template <typename T,class... U> void in(T &t,U &...u){ _cin(t); in(u...);}
void out(){cout << endl;} template <typename T,class... U> void out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ' '; out(u...);}
void dbg_out(){cout << endl;} template <typename T,class... U> void dbg_out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ','; out(u...);}
template<typename C> inline void in(vector<C> &v,int N=-1){if(sz(v) != 0){int M=(N == -1) ? sz(v) : N; rep(i,M) _cin(v[i]);}else{C c;rep(i,N) v.pb((_cin(c),c));}} template<typename C> inline void in(C v[],int N){rep(i,N) _cin(v[i]);}
template<typename C> inline void out(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<endl; } template<typename C> inline void out(C v[],int N){rep(i,N) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<endl; }
template<typename C> inline void vector_debug(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?", ":"" ); _cout(v[i]);} cout<<"}"<<endl; } template<typename C> inline void vector_debug(C v[], int N){rep(i,N) {cout<<((i)?", ":""); _cout(*(v+i));} cout<<"}"<<endl;}
template<typename C> inline C vmax(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amax(n,v[i]); return n;} template<typename C> inline C vmax(C v[], int N){C n=v[0]; rep( i , N ) amax(n,v[i]); return n;}
template<typename C> inline C vmin(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amin(n,v[i]); return n;} template<typename C> inline C vmin(C v[], int N){C n=v[0]; rep( i , N ) amin(n,v[i]); return n;}
template<typename C> inline C vsum(const vector<C> &v){C n=0; rep(i,sz(v)) n+=v[i]; return n;} template<typename C> inline C vsum(C v[], int N){C n=0; rep( i , N ) n+=v[i]; return n;}
const int dx[]={1,0,-1,0}; const int dy[]={0,1,0,-1};
//const int dx[]={1,1,1,0,-1,-1,-1,0}; const int dy[]={1,0,-1,-1,-1,0,1,1};

// ini(A,B,C) => int A,B,C; cin >> A >> B >> C; 
// in(A,B,C) => cin >> A >> B >> C;   invi(v,N) =>vi v; rep(i,N) v.pb( (int x,cin >> x,x) );
// out(A,B,C) cout << A << ' ' <<  B << ' ' << C;
// in,outともにベクトル・配列・pairに使用可能(ただしベクトル・配列は１つしか入れられない)
// amax(x,y) bool関数　x<yの時にxにyを代入してtrueを返す

// mod
inline ll madd(ll a, ll b){return (a + b) % mod;}
inline ll msub(ll a, ll b){return (a + mod - b) % mod;}
inline ll mmul(ll a, ll b){return ((a % mod) * (b % mod)) % mod;}
ll mpow(ll a, ll b){if(b == 0) return 1; else if(b == 1) return a % mod; else if(b % 2 == 0){ll hlf = mpow(a,b/2);return (hlf * hlf) % mod;} else {ll hlf = mpow(a,b/2);return ( mmul(hlf , hlf) * a ) % mod;}}
inline ll mdiv(ll a, ll b){return mmul(a, mpow(b, mod-2));}

ll fct[200010];
void f(int M){
    rep(i,M+1){
        if(i == 0) fct[i] = 1;
        else fct[i] = mmul(fct[i-1],i);
    }
}

constexpr int an = 200010;
int N;

int A[an]; // 深さを記入する配列
void bfs(int src, vvi &v){
    rep(i,N+1) A[i] = -1; // Aの初期化
    queue<int> Q;
    Q.push(src);
    A[src] = 1; // A[スタート地点]の深さ = 0
    while(! Q.empty()){
        int cur = Q.front();
        trc(cur);
        Q.pop();
        for(int x : v[cur]){ // 探索範囲
            if(A[x] == -1){ // 条件
                int dst = x;
                A[dst]=A[cur]+1; // dstの深さはA[cur]+1
                Q.push(dst); // Qにdstを追加
            }
        }
    }
}

int main(){
    in(N);
    f(N);
    vdbg(fct,N+1);
    vvi v(N+1);
    rep(i,N-1){
        ini(u,V);
        v[u].pb(V); v[V].pb(u);
    }
    vdbg(v[1]); vdbg(v[2]);
    bfs(1,v);
    ll ans = 0;
    for(int i=1; i<=N; i++){
        ans = madd( ans, mdiv(fct[N] , A[i]) );
    }
    out(ans);
}

yukicoder

結果

テストケース

ソースコード