2021.05.03 T3 数字
2021.05.03 T3 数字
问题描述
一个数字被称为好数字当他满足下列条件:
1. 它有**2*n**个数位,n是正整数(允许有前导0)
2. 构成它的每个数字都在给定的数字集合S中。
3. 它**前n位之和与后n位之和相等**或者它**奇数位之和与偶数位之和相等**
例如对于n=2,S={1,2},合法的好数字有1111,1122,1212,1221,2112,2121,2211,2222这样8种。
已知n,求合法的好数字的个数mod 999983。
输入
第一行一个数n。
接下来一个长度不超过10的字符串,表示给定的数字集合。
输出
一行一个数字表示合法的好数字的个数mod 999983。
样例输入
2
0987654321
样例输出
1240
数据范围
对于20%的数据,n≤7。
对于100%的.据,n≤1000,|S|≤10。
分析:
设f[i][j]为当数字规模为i且各数为位数字之和为j时的好数字个数,f[i+1][j+s[k]]的方案数中一定有f[i][j]的方案数,所以f[i+1][j+s[k]]=f[i][j]+f[i+1][j+s[k]]。把左半部分看成一个名为A的位置,把右半部分看成一个名为B的位置,A和B上都有f[i][j]中方案数,则在i与j一定时,一共有A*B种方案数。
把n个数划分为i部分,则i的取值范围是1n,当i=0是,A(或B)这一位置上只有一种放法——什么都不放,在这一题就是没有任何方案.当i个位置上所有数字全是9时,j最大,j的取值范围是sminismaxi,但集合s中不一定有9,所以需要判断一下smax与smin,实际上不用单独找,sort排序一下或直接判断有没有f[i][j]。
前后和相等和奇偶位和相等与每个小位置上具体是哪个数字以及到底有那些数字无关,只与和有关,所以前后和相等的方案数与奇偶位和相等的方案数相等。设总方案数为ans,ans=奇偶位和相等的方案数+前后位和相等的方案数-前后位相等的方案数与奇偶位和相等的方案数的交集。
当前后位和相等的方案数=奇偶位和相等的方案数时,前位奇数位和=后位偶数位和,前位偶数位和=后位奇数位和,当从集合s中选取的数字不变时,前位奇数位和可以做后位奇数位和。设前位奇数位和为C,则与之相对的后位奇数为和为D,则交集方案数为C*D。
PS:
if(f[x][i])fin=(fin+(ll)f[x][i]*f[x][i])%mod;
此处如果先乘后转为long long会爆int,所以不能把ll后面的乘法用括号括住
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define mod 999983
typedef long long ll;
int n,s[12],f[1005][9005];
ll ans=0;
string si;
ll add(int x){
ll fin=0;
for(int i=0;i<=x*9;i++)
if(f[x][i])fin=(fin+(ll)f[x][i]*f[x][i])%mod;
return fin;
}
int main(){
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
cin>>n>>si;
for(int i=0;i<si.size();i++)s[i+1]=si[i]-'0';
sort(s+1,s+si.size()+1);
f[0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=n*9;j++){
if(f[i][j]){
for(int k=1;k<=si.size();k++){
f[i+1][j+s[k]]=(f[i+1][j+s[k]]+f[i][j])%mod;
}
}
}
}
ans=(2*add(n)-add(n/2)*add(n-n/2))%mod;
cout<<(ans+mod)%mod;
return 0;
}
最新文章
- Python之路第一课Day2--随堂笔记
- asp.net初识
- ESB 中的流量控制
- Graphics samples2
- UCOS-互斥信号量(学习笔记)
- uistepper on ios versions prior to 5.0
- UIAlertController基本使用
- Baidu Sitemap Generator插件使用图解教程
- VS 2013上Python的配置
- MyBatis深入理解一
- css以及选择器基础
- 安卓中不同APP之间的消息通信
- JavaScript深度克隆(递归)
- 从零开始学HTTP (一)网络基础
- #WEB安全基础 : HTTP协议 | 0x1 TCP/IP通信
- AJAX初尝试——ACM/ICPC类比赛气球管理系统
- C#.NET常见问题(FAQ)-如何强制退出进程
- 在程序开发中怎样写SQL语句可以提高数据库的性能
- Java获取Resource目录下的文件
- 灾难恢复:RPO与RTO
热门文章
- session 会话机制以及变量覆盖
- 二叉树:前序遍历、中序遍历、后序遍历,BFS,DFS
- UNIX网络编程--学习日记
- dev编译器兼容设置及字符串的识别问题
- JDK8新特性关于Stream流
- JAVA 用命令提示符执行java找不到或者无法加载主类
- java 队列
- Error running &#39;App&#39;: Command line is too long. Shorten command line for App or also for Spring Boot default configuration.
- Spring Cloud 解决了哪些问题?
- 描述一下 DispatcherServlet 的工作流程 ?