[SDOI2010] 地精部落 (组合数学,动态规划)

2024-09-08 14:22:10

题目链接

Solution

很巧妙的 DP。

可以看这里的题解。

比我自己讲要好的多。

Code

#include <bits/stdc++.h>

using namespace std;

int n,p,f[2][5000];

int main()

{

    cin>>n>>p;

    bool t=0;

    f[t][1]=1;

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

        t=!t;

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

            f[t][j]=(f[t][j-1]+f[!t][i-j])%p;

    }

    cout<<f[t][n]*2%p;

    return 0;

}

最新文章

热门文章