hdu 4901 DP 交了20+遍！

今天药忘吃喽~ 2022-08-10 14:51 5阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=4901][http_acm.hdu.edu.cn_showproblem.php_pid_4901]

题目大意：把n个数分成两个组s和t（不是所有数都要），s组中的所有数都在t的左边，s中的数进行xor运算，t中的数进行and运算，求结果相等的组合数。xor和and的运算结果遵循结合律，所以是不分顺序的。

题解：实在无力吐槽自己是有多坑，这题解题报告上说是水题的题目，我前后交了20多遍才对 = =。也是菜。比赛的时候，我也是想到了计数DP的方法，也想到了fX\[i\]\[j\]表示从前面开始，用第i个数XOR构成j的结果的组合数,fA\[i\]\[j\]表示从后开始用第i个数and运算构成j的结果的情况数，用sX\[i\]\[j\]表示用前i个数的构成j的总情况数，也就是1~i的f\[i\]\[j\]的总和，sA类似。这样就可以用fX\[i\]\[j\]\*sA\[i+1\]\[j\](i~(1,n),j~(0~1023))的和求出答案，理解起来的话，i和i+1就是一个分界，第i个数必定属于s组，第i+1个数不一定在t组里，这样因为s都不一样，所以所有组合都不会一样。

我错误的点主要有2个，第一个严重的错误是在算fX\[i\]\[j\]的时候，简单的加上了fX\[i-1\]\[j\]以为这样就可以把所有情况加上去，其实应该是用sX\[i\]\[j\]这里面才是记的总和，错误的代码在下面划斜杠的部分，第二个错误是在算ans的时候，我一开始只写了ans+=((ll)fX\[i\]\[k\]\*sA\[i+1\]\[k\])%M，我忽略了将ans加和之后的结果也modM。这个错误我很久都没发现，如果只是因为这个错误错了，那该是有多坑。。记在这里提醒自己。

沧桑的代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    typedef __int64 ll;
    #define M 1000000007
    ll ans;
    int a[1001],k,i,l,j,n,T,fA[1001][1024],fX[1001][1024],sX[1001][1024],sA[1001][1024];
    
    void init()
    {
        memset(sX,0,sizeof(sX));
        memset(sA,0,sizeof(sA));
        memset(fX,0,sizeof(fX));
        memset(fA,0,sizeof(fA));
        scanf("%d",&n);
        ans=0;
        for (i=1;i<=n;i++)
            scanf("%d",&a[i]);
    }
    
    int main()
    {
        scanf("%d",&T);
        while (T--)
        {
            init();
            fX[1][a[1]]=sX[1][a[1]]=1;
            fA[n][a[n]]=sA[n][a[n]]=1;
            for (i=2;i<=n;i++)
            {
                fX[i][a[i]]=1;
                for (j=0;j<1024;j++)
                    fX[i][j^a[i]]=(fX[i][j^a[i]]+sX[i-1][j])%M;
                for (j=0;j<1024;j++)
                    sX[i][j]=(sX[i-1][j]+fX[i][j])%M;
            }
            for (i=n-1;i>=1;i--)
            {
                fA[i][a[i]]=1;        
                for (j=0;j<1024;j++)
                    fA[i][j&a[i]]=(fA[i][j&a[i]]+sA[i+1][j])%M;
                for (j=0;j<1024;j++)
                    sA[i][j]=(sA[i+1][j]+fA[i][j])%M;
            }
            //for (i=1;i<=n;i++)
            //    for (j=0;j<=1024;j++)
            //    sX[i][j]+=sX[i-1][j]+fX[i][j];
            //sA[n][a[n]]=1;
            //for (i=n-1;i>=1;i--)
            //    for (j=0;j<1024;j++)
            //    sA[i][j]=(sA[i+1][j]+fA[i][j])%M;
            for (i=1;i<n;i++)
                for (k=0;k<1024;k++)
                {
                    ans+=((ll)fX[i][k]*sA[i+1][k])%M;
                    ans%=M;
                }
            printf("%I64d\n",ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4901]: http://acm.hdu.edu.cn/showproblem.php?pid=4901