5.21总结

考试总结:

t1发现数据是n逐渐升高的,就开始害怕起来,想了一下发现只会10分,想了想好像有nlogn个gcd,难道是分块???在脑子里xx了一下,很有道理,打出来发现代码细节多,太恶心了,于是打50分,发现我求出的量不是答案,是总方案数,此时快要9点,打了10分的暴力,就走了,看了一眼t2,10分很简单,下一档直接100,就走了,看t3,看起来好像可做的样子,但是不会和生成函数有关吧???毕竟是图计数,发现直接求方案数是O(n)的,顿时信心倍增,搞了一会,嗯嗯嗯???还是不明白怎么把序列的信息,与逆序对对应起来,于是打了t3的25分暴力,回去打了t2的10分,考试就结束了

t3:

f [x][pos][w] 在以x为根的子树的拓扑序上w在第pos个位置

5.21总结

更新f分成v-->x 和 x-->v

核心代码:

for (int pos = 1; pos <= siz[y]; pos++)
        for (int w = 1; w <= n; w++)
            if (f[y][pos][w])
                for (int c = 0; c < siz[x]; c++)  // x的拓扑序的最后一个必须是x
                {
                    int res = 1ll * f[y][pos][w] * C[c + pos - 1][pos - 1] % p *
                              C[siz[x] + siz[y] - pos - c - 1][siz[y] - pos] % p;
                    f[x][pos + c][w] = (f[x][pos + c][w] + 1ll * wx * res) % p;
                    int a = sum[c][n] - sum[c][w], b = sum[siz[x]][w] - sum[c][w];  // b -1
                    g[x] = (g[x] + 1ll * res * (a + b) % p) % p;
                }

 

上一篇:5.21模拟赛总结


下一篇:腾讯T3团队整理,好文推荐