bzoj1925(SCOI2010)地精部落

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1925

要怎样才能想出正解呢？

当然有一维表示从1到 i 。

　　发现最后是递增的方案数=最后是递减的方案数，因为其实按值把 j 变成 i - j + 1 就行了。所以记一个递增或递减，ans*=2就行了。

指定新来一个数只能加到末尾，所以第二维记录末尾的数是 j 且是递增或递减；

如果新来的数只能加到末尾，怎么保证求了所有情况？

　　需要换个想法：不是前 i 个数，而是前n个数里的 i 个数；不是末尾是 j ，而是末尾是第 j 小的数。

　　因为最后会求满n个数，所以前期不用乘什么（比如1324不用乘什么来涵盖2435，因为在一共有n个数的时候，5就会出现在后面了）。

　　这样好像就不错了。

怎么推？来自阿当学长的博客：https://blog.csdn.net/aarongzk/article/details/44871391

　　发现递增和递减之间有两个关系：如果用f [ ] [ ]表示最后递增，g [ ] [ ] 表示最后递减，则

　　f [ i ] [ j ] = ∑(k∈[1,j-1])g [ i-1 ] [ k ]；g [ i ] [ j ] = f [ i ] [ i - j + 1 ]；

　　于是 f [ i ] [ j ] = ∑(k∈[1,j-1]) f [ i - 1 ] [ i - j ]；

　　即　f [ i ] [ j ] = ∑(k∈[i-1,i-j+1]) f [ i - 1 ] [ k ]；

　　发现f [ i ] [ j-1 ] = ∑(k∈[i-1,i-j+2]) f [ i - 1 ] [ k ]；

　　所以f [ i ] [ j ] = f [ i ] [ j - 1 ] + f [ i - 1 ] [ i - j + 1 ]；

　　真是太美好了。

但是自己怎么才能想出来呢？

　　首先第二维按套路应该记一个具体的数。然后发现递增和递减的微妙等价关系，于是设计两个数组表示递增和递减，最后推得美妙式子吗？

　　前提是思想灵活一点，就能知道可以指定新来的数加在最后面，进而得出种种状态设计吧。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=;

int n,p,f[][N],ans;

int main()

{

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

    f[][]=;//因为f[1][1]=1

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

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

            f[i&][j]=(f[i&][j-]+f[(i-)&][i-j+])%p;

    for(int j=;j<=n;j++)

        (ans+=f[n&][j])%=p;

    (ans<<=)%=p;

    printf("%d",ans);

    return ;

}

巴特西

bzoj1925(SCOI2010)地精部落

最新文章

热门文章