hihoCoder 1367 等式填空

明确题意

等号左边是由'+'和'?'组成的算式，其中处于某个整数(即便这个整数只有一位)首位的'?'可以填入1-9中的某个数字，其余'?'可以填入0-9中的某个数字。

SOURCE

这里未明确等号左边有几个整数（至少有一个）。读题时我未能仔细理解这句话的含义，根据样例误认为有且仅有两个整数相加。另外，等号右边的非负整数，题目虽未明确是否有前导零，可以认为没有（不应该在这里纠结题意）。

做题的第一步是读题，诚哉斯言！

解法

数位DP。

将等号右边的非负整数的数位，按从低位到高位的顺序从1开始编号。

$dp[i][j]$：满足前 $i$ 位且对第 $i+1$ 位的进位是 $j$ 的方案数

$n$ 个正整数相加，每一位向前一位的进位都小于 $n$

状态转移便转化成了组合计数问题。

将 $n$ 个相同的球放进 $m$ 个不同的盒子里，每个盒子里最多放 $9$ 个球。在这 $n$ 个盒子中指定 $k$ 个，其中每个盒子里至少放一个球。求方案数。

由于放进的球数有上限，并不能用挡板法。

做法：枚举分配到 $k$ 个非空盒子的球的总数，分别计算两类盒子的放置方案数，这两个计数问题都可采用简单的DP解决。

总复杂度：$O(n^2+mn3)$，$n$ 是等号左边的数（加数）的个数，$m$ 是等号右边数（和）的位数。

练习题

hihoCoder 1076 与链

Implementation

#include <bits/stdc++.h>

using namespace std;

const int N=105;

long long dp[N][50];

const int mod=1e9+7;

char s[N];

int c[2][50][500];

void prep(int n)

{

    c[1][0][0]=c[0][0][0]=1;

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

    {

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

        {

            for(int k=1; k<=min(9, j-i+1); k++)

            {

                c[1][i][j]+=c[1][i-1][j-k], c[1][i][j]%=mod;

            }

        }

        for(int j=0; j<=9*i; j++)

        {

            for(int k=0; k<=min(9, j); k++)

            {

                c[0][i][j]+=c[0][i-1][j-k], c[0][i][j]%=mod;

            }

        }

    }

}

vector<int> a;

int main()

{

    int ma=0;

    for(; ; )

    {

        int len;

        scanf("%*[?]%n%[=+]", &len, s);

        a.push_back(len);

        ma=max(ma, len);

        if(s[0]=='=')

        {

            break;

        }

    }

    int n;

    scanf("%s%n", s+1, &n);

    if(n<ma)

    {

        puts("0");

        return 0;

    }

    prep(a.size());

    reverse(s+1, s+n+1);

    dp[0][0]=1;

    int carry=a.size();

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

    {

        int cnt1=0, cnt2=0;

        for(auto x: a)

        {

            cnt1+=x==i;

            cnt2+=x>i;

        }

        for(int j=0; j<carry; j++)

            for(int k=0; k<carry; k++)

            {

                int tot=s[i]-'0'+10*j-k;

                long long sum=0;

                for(int l=cnt1; l<=tot; l++)

                {

                    sum+=(long long)c[1][cnt1][l]*c[0][cnt2][tot-l];

                    sum%=mod;

                }

                dp[i][j]+=dp[i-1][k]*sum;

                dp[i][j]%=mod;

            }

    }

    cout<<dp[n][0]<<endl;

    return 0;

}

巴特西

hihoCoder 1367 等式填空

明确题意

解法

练习题

Implementation

最新文章

热门文章