Submission #933463


Source Code Expand

#include <algorithm>
#include <set>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }

const LL MOD=LL(1e9)+7;

int main() {
    int n, m, k; scanf("%d%d%d", &n,&m,&k);
    vector<VI> es(n);
    repn(i, m) {
        int a, b; scanf("%d%d", &a,&b);
        --a, --b;
        es[a].pb(b), es[b].pb(a);
    }

    VI vis(n, 0), dfn(n), low(n);
    vector<VPI> comps;
    VPI stack;
    int label=0;
    const function<void(int, int)> dfs=[&](int x, int fa) {
        dfn[x]=low[x]=label++;
        vis[x]=-1;
        for(int y: es[x]) if(y!=fa && vis[y]<=0) {
            stack.pb(mp(x, y));
            if(vis[y]==0) {
                dfs(y, x);
                if(low[y]>=dfn[x]) {
                    VPI comp;
                    do {
                        comp.pb(stack.back());
                        stack.pop_back();
                    } while(comp.back()!=mp(x, y));
                    comps.pb(comp);
                }
                setmin(low[x], low[y]);
            } else {
                setmin(low[x], dfn[y]);
            }
        }
        vis[x]=1;
    };
    repn(x, n) if(vis[x]==0) dfs(x, -1);

    const int N=210;
    static LL pow[N], inv[N], binom[N][N];
    const auto power=[&](LL a, LL b) {
        LL c=1;
        for(; b>0; b>>=1, a=a*a%MOD)
            if(b&1) c=c*a%MOD;
        return c;
    };
    pow[0]=1;
    rep(i, 1, N-1) pow[i]=(pow[i-1]*k)%MOD;
    rep(i, 1, N-1) inv[i]=power(i, MOD-2);
    repn(i, N) binom[i][0]=binom[i][i]=1;
    rep(i, 1, N-1) rep(j, 1, i-1) binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%MOD;

    LL ans=1;
    for(const auto& c: comps) {
        if(sz(c)==1) {
            (ans*=k)%=MOD;
            continue;
        }
        set<int> s; for(PII p: c) s.insert(p.fi), s.insert(p.se);
        //cout<<sz(c)<<" "<<sz(s)<<": "<<c<<" "<<VI(all(s))<<endl;
        if(sz(c)==sz(s)) {
            LL tmp=0;
            rep(i, 1, sz(c)) (tmp+=pow[gcd(i,sz(c))])%=MOD;
            (tmp*=inv[sz(c)])%=MOD;
            (ans*=tmp)%=MOD;
        } else {
            (ans*=binom[k+sz(c)-1][sz(c)])%=MOD;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User fqw
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 3640 Byte
Status AC
Exec Time 3 ms
Memory 640 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:47:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int n, m, k; scanf("%d%d%d", &n,&m,&k);
                                           ^
./Main.cpp:50:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d%d", &a,&b);
                                       ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 64
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt
Case Name Status Exec Time Memory
0_000.txt AC 3 ms 640 KB
0_001.txt AC 3 ms 640 KB
0_002.txt AC 3 ms 640 KB
1_003.txt AC 3 ms 640 KB
1_004.txt AC 3 ms 640 KB
1_005.txt AC 3 ms 640 KB
1_006.txt AC 3 ms 640 KB
1_007.txt AC 3 ms 640 KB
1_008.txt AC 3 ms 640 KB
1_009.txt AC 3 ms 640 KB
1_010.txt AC 3 ms 640 KB
1_011.txt AC 3 ms 640 KB
1_012.txt AC 3 ms 640 KB
1_013.txt AC 3 ms 640 KB
1_014.txt AC 3 ms 640 KB
1_015.txt AC 3 ms 640 KB
1_016.txt AC 3 ms 640 KB
1_017.txt AC 3 ms 640 KB
1_018.txt AC 3 ms 640 KB
1_019.txt AC 3 ms 640 KB
1_020.txt AC 3 ms 640 KB
1_021.txt AC 3 ms 640 KB
1_022.txt AC 3 ms 640 KB
1_023.txt AC 3 ms 640 KB
1_024.txt AC 3 ms 640 KB
1_025.txt AC 3 ms 640 KB
1_026.txt AC 3 ms 640 KB
1_027.txt AC 3 ms 640 KB
1_028.txt AC 3 ms 640 KB
1_029.txt AC 3 ms 640 KB
1_030.txt AC 3 ms 640 KB
1_031.txt AC 3 ms 640 KB
1_032.txt AC 3 ms 640 KB
1_033.txt AC 3 ms 640 KB
1_034.txt AC 3 ms 640 KB
1_035.txt AC 3 ms 640 KB
1_036.txt AC 3 ms 640 KB
1_037.txt AC 3 ms 640 KB
1_038.txt AC 3 ms 640 KB
1_039.txt AC 3 ms 640 KB
1_040.txt AC 3 ms 640 KB
1_041.txt AC 3 ms 640 KB
1_042.txt AC 3 ms 640 KB
1_043.txt AC 3 ms 640 KB
1_044.txt AC 3 ms 640 KB
1_045.txt AC 3 ms 640 KB
1_046.txt AC 3 ms 640 KB
1_047.txt AC 3 ms 640 KB
1_048.txt AC 3 ms 640 KB
1_049.txt AC 3 ms 640 KB
1_050.txt AC 3 ms 640 KB
1_051.txt AC 3 ms 640 KB
1_052.txt AC 3 ms 640 KB
1_053.txt AC 3 ms 640 KB
1_054.txt AC 3 ms 640 KB
1_055.txt AC 3 ms 640 KB
1_056.txt AC 3 ms 640 KB
1_057.txt AC 3 ms 640 KB
1_058.txt AC 3 ms 640 KB
1_059.txt AC 3 ms 640 KB
1_060.txt AC 3 ms 640 KB
1_061.txt AC 3 ms 640 KB
1_062.txt AC 3 ms 640 KB
1_063.txt AC 3 ms 640 KB