Sort by

recency

|

4 Discussions

|

  • + 0 comments

    include

    include

    include

    using namespace std;

    typedef long long s64;

    const int MaxD = 200000;

    const int MaxTN = 524288; const int FFT_P = 1005060097; const int FFT_G = 5;

    inline int modpow(int a, s64 n) { int t = a; int res = 1; for (s64 i = n; i > 0; i >>= 1) { if (i & 1) res = (s64)res * t % FFT_P; t = (s64)t * t % FFT_P; } return res; }

    int fftG[MaxTN];

    void fft(int n, int step, int *a, int *out) { if (n == 1) { out[0] = a[0]; return; }

    int m = n >> 1;
    fft(m, step + 1, a, out);
    fft(m, step + 1, a + (1 << step), out + m);
    for (int i = 0; i < m; i++)
    {
        int e = out[i], o = (s64)out[i + m] * fftG[i << step] % FFT_P;
        out[i] = (e + o) % FFT_P;
        out[i + m] = (e + FFT_P - o) % FFT_P;
    }
    

    }

    void polymul(int n, int *a, int *b, int *c) { int g = modpow(FFT_G, (FFT_P - 1) / n); fftG[0] = 1; for (int i = 1; i < n; i++) fftG[i] = (s64)fftG[i - 1] * g % FFT_P;

    static int fa[MaxTN];
    static int fb[MaxTN];
    
    fft(n, 0, a, fa);
    fft(n, 0, b, fb);
    
    reverse(fftG + 1, fftG + n);
    
    for (int i = 0; i < n; i++)
        fa[i] = (s64)fa[i] * fb[i] % FFT_P;
    
    fft(n, 0, fa, c);
    
    int revN = modpow(n, FFT_P - 2);
    for (int i = 0; i < n; i++)
        c[i] = (s64)c[i] * revN % FFT_P;
    
    /*
    fill(c, c + n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[(i + j) % n] = (c[(i + j) % n] + (s64)a[i] * b[j]) % FFT_P;*/
    

    }

    int calc(int n, int d) { static int fact[MaxD + 1]; fact[0] = 1; for (int x = 1; x <= d; x++) fact[x] = (s64)fact[x - 1] * x % FFT_P; static int rfact[MaxD + 1]; rfact[1] = 1; for (int x = 2; x <= d; x++) rfact[x] = (FFT_P - (s64)(FFT_P / x) * rfact[FFT_P % x] % FFT_P) % FFT_P; rfact[0] = 1; for (int x = 1; x <= d; x++) rfact[x] = (s64)rfact[x] * rfact[x - 1] % FFT_P;

    static int a[MaxTN];
    static int b[MaxTN];
    
    int tn = 1;
    while (tn < (d + 1) * 2)
        tn <<= 1;
    
    fill(a, a + tn, 0);
    fill(b, b + tn, 0);
    
    for (int i = 0; i <= d; i++)
        a[i] = (s64)rfact[i] * modpow(i, d) % FFT_P;
    for (int i = 0; i <= d; i++)
        b[i] = (s64)rfact[i] * modpow(FFT_P - 1, i) % FFT_P;
    
    static int strl2[MaxTN];
    polymul(tn, a, b, strl2);
    
    /*
    for (int i = 0; i <= d; i++)
    {
        strl2[i] = 0;
        for (int j = 0; j <= i; j++)
        {
            int cur = (s64)rfact[j] * modpow(j, d) % FFT_P * rfact[i - j] % FFT_P * modpow(FFT_P - 1, i - j) % FFT_P;
            strl2[i] = (strl2[i] + cur) % FFT_P;
        }
    }
    */
    
    /*
    strl2[0] = 1;
    for (int i = 1; i <= d; i++)
    {
        strl2[i] = 0;
        for (int j = i; j >= 1; j--)
            strl2[j] = ((s64)strl2[j] * j + strl2[j - 1]) % FFT_P;
        strl2[0] = 0;
    }*/
    
    int res = 0;
    for (int k = 0, n_k = 1; k <= min(d, n); n_k = (s64)n_k * (n - k) % FFT_P, k++)
    {
        int cur = (s64)strl2[k] * n_k % FFT_P * modpow(2, n - k) % FFT_P;
        res = (res + cur) % FFT_P;
    }
    return res;
    

    }

    int main() { int nT; cin >> nT; while (nT--) { int n, d; scanf("%d %d", &n, &d);

        n--;
        int res = (s64)(n + 1) * modpow(2, (s64)n * (n - 1) / 2) % FFT_P;
        res = (s64)res * calc(n, d) % FFT_P;
        printf("%d\n", res);
    }
    
    return 0;
    

    }

  • + 0 comments

    So, funny story: I spent many hours over the last two days poring over identities involving binomial coefficients, in hopes of massaging a sum that took O(K^2) into a sum that takes O(K). I assumed that there had to be some kind of combinatorial trick involving Pascal's triangle, because otherwise how could this challenge be possible? Anyway, I finally found one, and everything passes.

    Lo and behold, the editorial mentions the same formula that I ended up finding --- as an alternative solution (submitted by bayleef). The intended method of solution from the editorial did not occur to me even once, and I'm sure I wouldn't ever have considered it even if I spent another two weeks on this problem. :-) Perhaps if I were more familiar with particular large primes, I might have taken the "unusual" modulus as a hint, but it was totally lost on me. :-)

    Anyway, kevinsogo mentions in the editorial that he couldn't see a proof that bayleef's formula gives the same answer as the naive (and slow) formula involving Stirling numbers; the comments in my submission outline the combinatorial argument that shows why the two formulas are equivalent.

    Please feel free to drop me a line if I can offer any assistance with solving this challenge in an apparently completely unintended way. :-)

  • + 1 comment

    In the third test case, if n=3, how can there be 3 edges without a loop? am I missing something trivial?

    • + 0 comments

      You are mixing loops and cycles.

  • + 1 comment

    can some one explain me what if n=4 and in case if there are three edges

    • + 0 comments

      This is one of my favourite sites and even though there are many such educational sites available Coffee beans ireland they aren’t up to this site as in this everything is well explained which made it easy for everyone to understand the topic

No more comments