课后自主练习(dp)1068. 变换种类数 super《编程思维与实践》个人学习笔记

题目

课后自主练习(dp)1068. 变换种类数 super《编程思维与实践》个人学习笔记
课后自主练习(dp)1068. 变换种类数 super《编程思维与实践》个人学习笔记

思路

①题目要求是对2、3、5、7可以整除,我们不妨取他们的最小公倍数210来进行状态统计(也可以开一个四维数组【2】【3】【5】【7】来记录状态)

②我们不妨先固定住一个位f(0,0) = 1(比如第零位0(因为没有第0位,就默认是0)先固定好,那么后续有以下情况,+1,-1,+12,-12,+123,-123)//需要注意题目的首字母没有-的情况,最后要除以2

A 对应的第一位 f ( 1 , 0 + 1 ) + = f ( 0 , 0 ) f(1,0+1) += f(0,0) f(1,0+1)+=f(0,0)//没有开头是负数的情况就不用管-1

B 接下来到第二位,第二位的可能是 +2 -2和×10+2
我们一开始先把*10+n的可能先列举完再处理+2-2的情况

但是×10+2的情况是从第0位跳到第2位的(0+12)
所以
f ( 2 , 12 ) + = f ( 0 , 0 ) f(2,12) += f(0,0) f(2,12)+=f(0,0)
而+2,-2,的情况是从第1位到第二位
于是有
f ( 2 , 1 + 2 ) + = f ( 1 , 1 ) f ( 2 , 1 − 2 ) + = f ( 1 , 1 ) f(2,1+2) += f(1,1) \quad f(2,1-2) += f(1,1) f(2,1+2)+=f(1,1)f(2,1−2)+=f(1,1)
由于我们状态没有负数和大于210的情况,我们应该把他们转换成对应的mod210的正整数(+210再%210)
f ( 2 , − 1 ) = f ( 2 , 209 ) f(2,-1) = f(2,209) f(2,−1)=f(2,209)

接下来再考虑第三位,有123,+3,-3,+23,-23这几种情况,显然我们有(这里忽略掉了210个状态,可以自己模仿上面的过程思考如何状态转移
f ( 3 ) + = ( 2 f ( 2 ) + 2 f ( 1 ) + f ( 0 ) ) f(3) += (2f(2) +2 f(1) + f(0)) f(3)+=(2f(2)+2f(1)+f(0))

③最后输出所有遍历整个字符串后,满足%2%3%5%7为0的数字即可

代码

#include<iostream>
#include<cstring>

#define ll long long
#define MOD (ll)(1e9 + 7)
using namespace std;

ll dp[300][210];
int arr[1000];

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        string s;
        cin >> s;
        memset(dp,0,sizeof(dp));
        memset(arr,0,sizeof(arr));
        dp[0][0] = 1;//默认不加数字是0,唯一的状态
        int len = s.length();
        for(int i = 0; i < len; i++)
        {
            arr[i] = s[i] - '0';
        }

        for(int i = 0; i < len; i++)
        {
            for(int rem = 0; rem < 210; rem++)
            {
                ll temp = 0;
                for(int j = i + 1; j <= len; j++)
                {
                    temp *= 10;
                    temp += arr[j - 1];
                    temp %= 210;

                    dp[j][(rem + temp) % 210] += dp[i][rem];
                    dp[j][(rem + temp) % 210] %= MOD;
                    
                    dp[j][(rem - temp + 210) % 210] += dp[i][rem];
                    dp[j][(rem - temp + 210) % 210] %= MOD;
                }
            }
        }
        
        ll ans = 0;
        for(int i = 0; i < 210; i++)
            if(!(i % 2) || !(i % 3) || !(i % 5) || !(i % 7))
            {
                ans += dp[len][i];
                ans %= MOD;
            }

        cout << ans * ((MOD + 1) / 2) % MOD << endl;
        //在mod里面除以2,找逆元
        //当然,在上面三重循环的过程中处理一下i=0,j=1没有-的情况也可以不进行逆元操作
    }

    return 0;
}


补充

何为逆元?
在加法运算中 +3的逆元就是-3,进行加法运算得到的0加上任何数字都不会改变他的大小
在乘法运算中 10的逆元就是0.1,乘法运算后得到的1乘任何数字也不改变他的大小

那在模运算中,就是让a×b后modc得到的余数是1的情况
比如
2 mod 5 == 2
2 × 3 mod 5 == 1
于是我们可以说3是2在mod5下的的逆元(通常记为3 == inv[2] (mod 5))
于是我们在mod某个数字p的时候,÷某个数相当于×他的逆元(类比9÷10 == 9×0.1)
所以在最后ans%1e9+7的时候想让ans/2,我们就找2的逆元
课后自主练习(dp)1068. 变换种类数 super《编程思维与实践》个人学习笔记
更多找逆元方法可以参考求逆元

上一篇:P5836 [USACO19DEC]Milk Visits S 从并查集到LCA(最近公共祖先) Tarjan算法


下一篇:PTA甲级 1068 Find More Coins (30point(s))