2021-2022-1 BUCT ACM集训队每周程序设计竞赛(8) - 问题D :一月忘干净
2021/11/22 11:09:55
本文主要是介绍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 :一月忘干净的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享