洛谷 P2523 [HAOI2011]Problem c

洛谷1或洛谷2，它们是一样的题目，手动滑稽～

这一题我是想不出来，

但是我想吐槽一下坐我左边的大佬。

大佬做题的时候，只是想了几分钟，拍了拍大腿，干脆的道：“这不是很显然吗！”

然后灵动地轻击键盘，不时抚弄头发，光速切紫题。

AC后笑眯眯地对我说，

你要是想的出来，我给你买一瓶2L可口可乐！不是在打广告～

我当然难以下手，但2L杀***水非常诱惑。

还是冥思苦想了一番，

大佬看着着急，就告诉了我状态定义，还笑着说，告诉你你也想不出方程。

我很生气，但身为蒟蒻又能怎样呢？

在大佬的不断提示下，我勉强把这题做了出来。

讲讲怎么做吧～

先看这题怎么样才算无解呢，

假设\(cnt[i]\)表示\(m\)个人中编号\(\ge i\)的个数。显然当\(cnt[i]>=n-i+1\)时无解。

大佬叫我这样定义状态\(f[i][j]\)表示剩下\(n-m\)个人中编号\(\ge i\)的人有\(j\)个。

所以，我们这么转移\(f[i][j]+=f[i+1][j-k]*C_{j}^{k}\)。

表示我们此时已经选了\(j-k\)人，再选\(k\)人的方案数。

注意事项：这是大佬的提醒～

因为方程是从\(i+1\)转移过来的，所以我们的\(i\)要倒过来枚举，答案显然是\(f[1][n-m]\)。

复杂度显然\(O(n^3)\)，当然还要乘上数据组数。

上代码～

#include <bits/stdc++.h>

using namespace std;

typedef int _int;

#define int long long

int n,m,mo,cnt[301],f[301][301];

int yh[301][301];

void pre()

{

    for (int i=0;i<=n;++i) yh[i][0]=1;

    for (int i=1;i<=n;++i) {

        for (int j=1;j<=i;++j) {

            yh[i][j]=yh[i-1][j-1]+yh[i-1][j];

            yh[i][j]%=mo;

        }

    }

}

_int main()

{

    int T;cin>>T;

    while (T--) {

        memset(f,0,sizeof(f));

        memset(cnt,0,sizeof(cnt));

        int x,y,flag=0;

        cin>>n>>m>>mo;

        for (int i=1;i<=m;++i) {

            cin>>x>>y;

            ++cnt[y];

        }

        for (int i=n;i;--i) {

            cnt[i]+=cnt[i+1];

            if (cnt[i]+i>n+1) {flag=1;break;}

        }

        if (flag) {puts("NO");continue;}

        pre();

        f[n+1][0]=1;int i,j,k;

        for (i=n;i;--i)

            for (j=0;j+i+cnt[i]<=n+1;++j)

                for (k=0;k<=j;++k)

                    f[i][j]+=(f[i+1][j-k]*yh[j][k]),f[i][j]%=mo;

        cout<<"YES "<<f[1][n-m]<<endl;

    }

    return 0;

}

巴特西

洛谷 P2523 [HAOI2011]Problem c

最新文章

热门文章