首页 > 其他分享 >题解:「2017 山东一轮集训 Day7」逆序对

题解:「2017 山东一轮集训 Day7」逆序对

时间:2024-11-12 20:22:35浏览次数:1  
标签:return int 题解 inv mmul Day7 2017 dp MOD

LibreOJ 6077

前置知识:生成函数、组合数


先考虑平方怎么做。\(f_{i,j}\) 表示处理了前 \(i\) 个值,逆序对有 \(j\) 个。显然可以转移到 \(f_{i+1,j},f_{i+1,j+1},f_{i+1,j+2},...,f_{i+1,j+i}\)。然后发现这个东西是个很简单的递推,而且长得很生成函数,于是可以很自然的写成

\[1\times (1+x)\times(1+x+x^2)\times(1+x+x^2+x^3)\times... \]

显然每一个乘数都是一个等比数列,所以根据小学学的等比数列求和公式,得到:

\[\sum_{i=1}^{n} \frac{1-x^i}{1-x} =\frac{1}{(1-x)^n}\sum_{i=1}^{n} (1-x^i) \]

然后左边那个系数是一个经典的生成函数,他相当于 \((1+x+x^2+x^3+...)^n\)。显然 \(i\) 次项的系数是 \(i\) 个物品分给 \(n\) 个人且可以不拿到的方案数,即 \(i+n-1 \choose n-1\)。

比较难处理的是右边的。

假设是 \(\sum (1+x^i)\),那么 \(k\) 次项系数就是满足:

  • 互不相同
  • 不大于 \(n\)
  • 和为 \(k\)

的正整数集合数,且 \(n,k \le 10^5\)。

根据「互不相同」「和为 \(k\)」这两个条件,容易想到 「集合大小最大为 \(\mathcal{O}(\sqrt{k})\)」 的经典结论。

然后考虑 dp。设 \(dp_{i,j}\) 表示选了 \(i\) 个数,和为 \(j\) 的方案数。初值是 \(dp_{0,0}=1\)

对于当前转移对象 \(dp_{i,j}\):

  • 若 \(1\) 没被选,则可以把通过将集合内的所有数 \(+1\) 得到,此时和增加 \(i\),即

\[dp_{i,j}\gets dp_{i,j} + dp_{i,j-i} \]

  • 若 \(1\) 被选了,则可以把通过将集合内的所有数 \(+1\),并补充一个 \(1\) 到集合内得到,此时和增加 \(i\),即

\[dp_{i,j}\gets dp_{i,j} + dp_{i-1,j-i} \]

但是还有一条限制——「不大于 \(n\)」。

转移过程中可能会出现集合内有数 \(>n\) 的情况,但是由于每次只会集体 \(+1\),所以那个 \(>n\) 的数一定是 \(n+1\)。因此有:

\[dp_{i,j}\gets dp_{i,j} - dp_{i-1,j-(n+1)} (j \ge n+1) \]

然后问题就都解决了。

时间复杂度 \(\mathcal{O}(k \min(n,\sqrt{k}))\)。

// Author: AquariusZhao
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, RTN = 500, MOD = 1e9 + 7;
int n, k, fac[N], inv[N], dp[RTN][N];
int ans;

inline int madd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
inline int msub(int x, int y) { return madd(x, MOD - y); }
inline int mmul(int x, int y) { return 1ll * x * y % MOD; }
inline int qpow(int x, int y) { int res = 1, t = x % MOD;
    while (y) { if (y & 1) res = mmul(res, t);
    t = mmul(t, t); y >>= 1; }
    return res; }
inline int mdiv(int x, int y) { return mmul(x, qpow(y, MOD - 2)); }

void init(int lmt)
{
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= lmt; i++)
        fac[i] = mmul(fac[i - 1], i);
    inv[lmt] = mdiv(1, fac[lmt]);
    for (int i = lmt - 1; i >= 1; i--)
        inv[i] = mmul(inv[i + 1], i + 1);
}

int C(int x, int y)
{
    if (x < y)
        return 0;
    if (y == 0)
        return 1;
    return mmul(fac[x], mmul(inv[x - y], inv[y]));
}

int main()
{
#ifdef aquazhao
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    init(2e5);
    cin >> n >> k;
    dp[0][0] = 1;
    int lmt = min(n, (int)(ceil(sqrt(k + k))));
    for (int i = 1; i <= lmt; i++)
        for (int j = i; j <= k; j++)
        {
            dp[i][j] = madd(dp[i][j - i], dp[i - 1][j - i]);
            if (j >= (n + 1))
                dp[i][j] = msub(dp[i][j], dp[i - 1][j - (n + 1)]);
        }
    for (int i = 0; i <= k; i++)
    {
        int sum = 0;
        for (int j = 0; j <= lmt; j++)
            sum = j & 1 ? msub(sum, dp[j][i]) : madd(sum, dp[j][i]);
        ans = madd(ans, mmul(C(k - i + n - 1, n - 1), sum));
    }
    cout << ans << endl;
    return 0;
}

标签:return,int,题解,inv,mmul,Day7,2017,dp,MOD
From: https://www.cnblogs.com/avalaunch/p/18542570

相关文章

  • 题解:[SCOI2016] 美味
    前置知识:可持久化线段树(主席树)洛谷3293[SCOI2016]美味问题有一个长度为\(n\)的序列\(a_1,a_2,...,a_n\)。每次询问给你\(b\)、\(x\),你需要求出\(\max\{a_i+x\bigoplusb\}\)。\(1\lel\ler\len\le2\times10^5,0\lea_i,b,x<10^5\)首先,有\(l,r\)应该......
  • AtCoder Beginner Contest 378 题解
    AtCoderBeginnerContest378题解比赛链接A-Pairing贪心#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){vector<int>a(5);for(inti=0;i<4;i++){intx;cin>>x;a[x]++;......
  • 题解:[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!
    前置知识:2-SAT题意[XIXOpenCup,GrandPrixofKorea]Dev,PleaseAddThis!在一张网格上有以下几种物品:空地(.)墙(#)星星(*)一个球(O)现在你要玩一个游戏。你可以让球朝上下左右某一个方向移动,但是一旦移动就必须走到底,也就是说直到前面是墙或者边界才能停。另外,如果你走......
  • 【题解】洛谷P7286:「EZEC-5」人赢
    P7286「EZEC-5」人赢可以想到对于每个数要找到比他大的数中下标最大的数,我们按照数的大小排序,我们维护原序列的一个指针,对于每个数如果比指针大那么就左移指针,可以思考下为什么:指针上的数比现在这个数要小那比后面的数都小,于是我们左移指针直到大于这个数,可以发现我们也在一直......
  • 【题解】洛谷P8346:最澄澈的空与海
    【题解】洛谷P8346:最澄澈的空与海猜结论题,本身其实很简单,在纸上画个差不多就能想出来,我一开始想二分图最大匹配,但是还是太大了,不可以。当一个二分图有且仅有一种解时,必定有节点的入度为\(1\)。我们想到有多种匹配的情况,可以想到如果这是一个环的情况,一个左边的点将他右边的点......
  • MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构,先把下标转成从\(0\)开始,以方便用同余描述位置。倍增。用二元组来表示位置:\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,......
  • CF 705 题解
    CF705题解AHulk模拟即可.BSpiderMan打sg表可以发现,奇数个球先手必败(sg=0),偶数先手必胜(sg=1).多个组合只要把sg值异或起来就好.CThor暴力模拟就可以了,用队列模拟.DAntMan结论:按照编号由小到大加入链表,每次尽量让答案最小贪心就是对的.若原来是......
  • 题解:洛谷 P5180 【模板】支配树
    在图论模拟赛被T4的有向图必经点硬控了\(10^9+7s\),写篇题解纪念一下。其实,求有向图的必经点,通法就是支配树。一些定义:支配点:在确定起点\(S\)的情况下,对于一个点\(k\),若存在\(x\),使得删除\(x\)以及与\(x\)连接的边后,\(x\)与\(k\),不再强连通,那么就称\(k\)为\(x......
  • 【题解】洛谷P3118: Moovie Mooving G
    洛谷P3118:MoovieMoovingG看到数据范围考虑状压,题目要求看的电影最少那就维护时间最大,我们设\(f_{i}\)为\(i\)状态最多可以看多久的电影,对于不在集合的点我们枚举转移。我们每个开始时间都对应一个截至时间,问能加入这个点,每个点花费时间是固定的,我们又要不间断所以我们找......
  • CF785D 题解
    CF题目luogu题目题解似乎清一色是同一个做法,这里给一个容斥的做法。首先枚举一个位置\(i\),设\([1,i]\)的左括号个数为\(p\),\([i+1,n]\)的右括号个数为\(q\),那么以\(i\)这个位置为分界点的合法括号数有\(\sum_{i=1}^{\min(p,q)}C_p^iC_q^i\)个。通过范德蒙德卷......