C/C++教程

2021-2022-1 BUCT ACM集训队每周程序设计竞赛(8) - 问题D :一月忘干净

本文主要是介绍2021-2022-1 BUCT ACM集训队每周程序设计竞赛(8) - 问题D :一月忘干净,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2021-2022-1 ACM集训队每周程序设计竞赛(8) - 问题D :一月忘干净

  • 题意:一个含有\(?\)和数字的字符串,\(?\)可以用\(0\)~\(9\)来代替,问你最后得到的数有多少个除以\(13\)余\(5\)

  • 题解:首先要知道在取模意义下,乘法和加法都是能直接算的,设\(dp[i][j]\)为在第\(i\)个位置,余数为\(j\)的方案数,根据当前的\(s[i]\)算出当前的余数从上一个状态转移过来就好了

  • 代码

    #include <bits/stdc++.h>
    
    using namespace std;
    const int N=1e6+10;
    const int mod=1e9+7;
    #define ll long long
    #define pb push_back
    
    int n;
    char s[N];
    ll dp[N][20];
    
    int main(){
        scanf("%s",s+1);
    
        n=strlen(s+1);
        dp[0][0]=1;
        for(int i=1;i<=n;++i){
            if(s[i]=='?'){
                for(int k=0;k<10;++k){
                    for(int j=0;j<13;++j){
                        dp[i][(j*10+k)%13]=(dp[i][(j*10+k)%13]+dp[i-1][j])%mod;
                    }
                }
            }
            else{
                for(int j=0;j<13;++j){
                    dp[i][(j*10+s[i]-'0')%13]=(dp[i][(j*10+s[i]-'0')%13]+dp[i-1][j])%mod;
                }
            }
        }
    
        printf("%lld\n",dp[n][5]);
    
        return 0;
    }
    
    
这篇关于2021-2022-1 BUCT ACM集训队每周程序设计竞赛(8) - 问题D :一月忘干净的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!