fjnu2013 스쿨 E(디지털 dp, 배열 조합)

제목:
10개의 숫자를 제시하고 각각 i가 a[i]개가 있음을 나타낸다. 이 숫자들을 물어보면 모두 11로 나누어진 수를 구성할 수 있는 개수를 사용해야 한다.
문제 풀이:
초기 상태 dp[i][j][x][y]는 전 i개수, j비트 기수, 기수와 x, 짝수와 y가 조건을 충족시키는 개수를 사용한다.분명히 이 메모리는 허용되지 않는다. 사실 짝수의 상태를 삭제할 수 있다. 왜냐하면 짝수의 개수는 총위수-기수수로 할 수 있고 총위수를 기록할 수 없기 때문이다.dp[i][j][x]가 되었지만 너무 커서 스크롤 그룹 dp[2][j][x]를 사용한 다음에 dp를 완성하고 기수를 매거하여 답을 얻는다.
이것은 종신이 BNU 11993을 각색한 것으로 제목이 아주 좋다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const ll MOD=10007;
const int maxn=105;
const int maxm=1005;
int num[10];
ll dp[2][105][1005];
ll C[1005][1005];

void Init()
{
    for(int i=0;i<=1000;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
    }
}

int main()
{
    Init();
    int T,sum,cnt;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        sum=cnt=0;
        for(int i=0;i<=9;i++)
        {
            scanf("%d",&num[i]);
            cnt+=num[i];
            sum+=num[i]*i;
        }
        memset(dp,0,sizeof dp);
        dp[0][0][0]=1;
        int now=0,pre=1;
        int tol=0;
        ll temp;
        for(int dig=9;dig>=0;dig--)
        {
            now^=1;
            pre^=1;
            tol+=num[dig];
            memset(dp[now],0,sizeof dp[now]);
            for(int i=0;i<=100;i++)
            {
                for(int j=0;j<=1000;j++)
                if(dp[pre][i][j])
                {
                    for(int a=0;a<=num[dig];a++)
                    {
                        temp=dp[pre][i][j];
                        int da=i+a;
                        int b=num[dig]-a;
                        int db=tol-da;
                        if(dig==0)
                        {
                            if(i==0)
                                temp=0;
                            else
                                temp=(temp*C[da-1][a])%MOD;
                            temp=(temp*C[db][b])%MOD;
                        }
                        else
                        {
                            temp=(temp*C[da][a])%MOD;
                            temp=(temp*C[db][b])%MOD;
                        }
                        dp[now][i+a][j+dig*a]=(dp[now][i+a][j+dig*a]+temp)%MOD;
                    }
                }
            }
        }
        ll ans=0;
        int dig=(cnt-cnt/2);
        for(int i=0;i<=sum;i++)
        {
            int j=sum-i;
            int t=abs(i-j);
            if(t%11==0)
                ans=(ans+dp[now][dig][i])%MOD;
        }
        printf("Case %d: ",cas);
        cout<<ans<<endl;
    }
    return 0;
}
/***

*/