问题陈述
AtCoder Land 公司出售写有英文字母的瓷砖。高桥想把这些瓷砖排成一排,做成一个铭牌。
求长度在 11 和 𝐾K 之间(包括 998244353998244353 )的由大写英文字母组成的字符串中,满足以下条件的字符串的个数:
- 对于满足 1≤𝑖≤261≤i≤26 的每个整数 𝑖i 都成立:
- 设 𝑎𝑖ai 是按词典顺序排列的 𝑖i 个大写英文字母。例如, 𝑎1=a1= 为
A
, 𝑎5=a5=E
, 𝑎26=a26=Z
. - 在字符串中, 𝑎𝑖ai 的出现次数介于 00 和 𝐶𝑖Ci 之间(包括首尾两次)。
- 设 𝑎𝑖ai 是按词典顺序排列的 𝑖i 个大写英文字母。例如, 𝑎1=a1= 为
限制因素
- 1≤𝐾≤10001≤K≤1000
- 0≤𝐶𝑖≤10000≤Ci≤1000
- 所有输入值均为整数
输入
输入内容由标准输入法提供,格式如下
𝐾K
𝐶1C1 𝐶2C2 …… 𝐶26C26
输入样本 1
2
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
样本输出 1
10
满足条件的 10 字符串是 A
, B
, C
, AA
, AB
, AC
, BA
, BC
, CA
, CB
。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
const long long eps=998244353;
long long a[30];
long long dp[30][1010];
long long C[1010][1010];
long long jc[1010],ny[1010];
long long ksm(long long a,long long b){
long long tmp=a%eps;
long long res=1;
while(b){
if(b%2) res=res*tmp%eps;
b/=2;
tmp=tmp*tmp%eps;
}
return res%eps;
}
void zh(){
jc[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%eps;
ny[n]=ksm(jc[n],eps-2);
for(int i=n-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%eps;
}
long long c(int x,int y){
return jc[x]%eps*ny[x-y]%eps*ny[y]%eps;
}
int main()
{
cin >> n ;
for (int i = 1; i <= 26; i++)
{
cin>>a[i];
}
zh();
dp[0][0]=1;//考虑前i个字母, 共选了j个,共要n个
for(int i=1;i<=26;i++){
for(int j=0;j<=n;j++){
for(int k=a[i];k>=0;k--){
if(j-k>=0){
dp[i][j]+=dp[i-1][j-k]*c(j,k)%eps;//j个位置放k个的方案数,然后其他的按原来的顺序放
dp[i][j]%=eps;//
}
}
}
}
long long ans=0;
for(int i=1;i<=n;i++){
ans=(ans+dp[26][i])%eps;
ans%=eps;
}
cout<<ans;
}
P1077 [NOIP2012 普及组] 摆花
题目描述
小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 𝑚m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 𝑛n 种花,从 11 到 𝑛n 标号。为了在门口展出更多种花,规定第 𝑖i 种花不能超过 𝑎𝑖ai 盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算,一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数 𝑛n 和 𝑚m,中间用一个空格隔开。
第二行有 𝑛n 个整数,每两个整数之间用一个空格隔开,依次表示 𝑎1,𝑎2,⋯ ,𝑎𝑛a1,a2,⋯,an。
输出格式
一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对 106+7106+7 取模的结果。
输入输出样例
输入 #1复制
2 4 3 2
输出 #1复制
2
说明/提示
【数据范围】
对于 20%20% 数据,有 0<𝑛≤8,0<𝑚≤8,0≤𝑎𝑖≤80<n≤8,0<m≤8,0≤ai≤8。
对于 50%50% 数据,有 0<𝑛≤20,0<𝑚≤20,0≤𝑎𝑖≤200<n≤20,0<m≤20,0≤ai≤20。
对于 100%100% 数据,有 0<𝑛≤100,0<𝑚≤100,0≤𝑎𝑖≤1000<n≤100,0<m≤100,0≤ai≤100。
NOIP 2012 普及组 第三题
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const long long eps=1e6+7;
long long a[110];
long long dp[110][110];//前i种选了j个
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
dp[0][0]=1;
for(int i=0;i<=n;i++) dp[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=a[i];k++){//当前的种类选了k个
if(j-k>=0){
dp[i][j]+=dp[i-1][j-k];
dp[i][j]%=eps;
}
}
}
}
cout<<dp[n][m];考虑了n个种类,选出了m个的方案数
}