hdu 5185 Equation（分析+DP）

题意：

Gorwin is very interested in equations. Nowadays she gets an equation like this
x1+x2+x3+⋯+xn=n, and here

0≤xi≤nfor1≤i≤nxi≤xi+1≤xi+1for1≤i≤n−1

For a certain n, Gorwin wants to know how many combinations of xi satisfies above condition.
For the answer may be very large, you are expected output the result after it modular m.

1≤T<20
1≤n≤50000
1≤m≤1000000000

思路：

相邻两个数，后者要么和前者相等，要么比前者大一。可以知道x1...xn用unique去重后一定是一段连续的数。

x1要么是0，要么是1。不可能从1以后的某个数开始。因为那样是不可能得到n的~

也就是x1...xn一定是从0或1开始的连续的一段数。

然后发现其实是从1开始的连续的一段数（0是来“凑热闹”的【凑个数】）

假设这连续的一段数是从1~k。可知k不超过sqrt(n)。

DP结构出来了。dp[i][j]：从1~i这 i 种数组成和为j的方案数。

*：无须担心组成和为j的xi的个数。【肯定不会超过n个，因为最小为1，就算全是1，最多也就n个】。少于n个前面用0补全。

dp[i][j]=dp[i][j-i]+dp[i-1][j-i]

*写出一些dp[i][j]以观察正确性。

代码：

int T,n,m;

int dp[320][50010];

int main(){

    cin>>T;

    rep(t,1,T){

        scanf("%d%d",&n,&m);

        int k=1;

        while(k*(k+1)<=2*n) ++k;

        --k;

        mem(dp,0);

        dp[0][0]=1;

        rep(i,1,k){

            rep(j,i,n){

                dp[i][j]=(dp[i][j-i]+dp[i-1][j-i])%m;

            }

        }

        int ans=0;

        rep(i,1,k) ans=(ans+dp[i][n])%m;

        printf("Case #%d: %d\n",t,ans);

    }

    return 0;

}

巴特西

hdu 5185 Equation（分析+DP）

最新文章

热门文章