快递空包网站建设,自己做个公司网站,校园网站建设开题报告,公众号文章制作模板题干#xff1a;
winterzz1准备考4级了#xff0c;现在winterzz1决定把世界上所有单词都背一遍#xff0c;winterzz1发现任意一个单词最多有A个连续的元音#xff0c;最多有B个连续的辅音。且单词最长长度为N#xff0c;winterzz1问你在满打满算的情况他需要背多少单词
winterzz1准备考4级了现在winterzz1决定把世界上所有单词都背一遍winterzz1发现任意一个单词最多有A个连续的元音最多有B个连续的辅音。且单词最长长度为Nwinterzz1问你在满打满算的情况他需要背多少单词
输入描述:
首先输入一个T(T100)表示有T组案例每组案例依次输入三个正整数N,A,BN5000,A50,B50;
输出描述:
输出winterzz1最多需要背多少单词结果mod(10^97)
示例1
输入
复制
2
2 2 2
500 20 30
输出
复制
702
175540856
备注:
元音字母为a,e,i,o,u其余21个字母均为辅音
解题报告 这题不算难其实。。。dp[i][j][k]就完事了。。。不过超时了10多次后发现是因为mod运算了太多次了把mod改成const就火速AC了、、、好气啊、、不过可能是因为dp的姿势不太正确应该可以先记忆下来然后快速幂直接解决一下。。 这题抽象出来的意思就是长度为n的01串其中连续1的个数不能超过x个连续0的个数不能超过y个。给定n,x,y问能构造出多少合法串。。然后再加强一下对0和1有两个对应的权值这就变成这道题了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#includectime
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll dp[5005][2][55];//0代表元音1代表辅音
const ll mod 1e97;
int n,a,b;
int main()
{int t;scanf(%d,t);while(t--) {scanf(%d%d%d,n,a,b);int up max(a,b);for(int i 0; in; i) {for(int j 0; j50; j) {dp[i][0][j]dp[i][1][j]0;//别只初始化到up因为有可能上次的up更大所以没有初始化完全。。。}}if(n 1) {puts(26);continue;}dp[1][0][1]5;dp[1][1][1]21;for(int i 2; in; i) {//更新元音的for(int j 1; jmin(i-1,b); j) dp[i][0][1] (dp[i][0][1] dp[i-1][1][j]*5ll%mod)%mod;for(int j 2; jmin(i,a); j) dp[i][0][j] dp[i-1][0][j-1]*5%mod;//更新辅音的for(int j 1; jmin(i-1,a); j) dp[i][1][1] (dp[i][1][1]dp[i-1][0][j]*21%mod)%mod;for(int j 2; jmin(i,b); j) dp[i][1][j] dp[i-1][1][j-1]*21%mod;}ll ans 0;for(int i 1; in; i) {for(int j 1; j50; j) {if(j a) ans (ans dp[i][0][j])%mod;if(j b) ans (ans dp[i][1][j])%mod;}}printf(%lld\n,ans);}return 0 ;}
/*
2
2 2 2
500 20 30
*/
还有一个10msAC的代码以后再补一下吧、、
这个代码大概意思就是先dp[i][j]算出所有的再减去连续a个元音的或者连续b个辅音的也不算难想到啊其实不知道比赛的时候在干什么。。唉可能还是自己苔菜了、、
#includebits/stdc.h
using namespace std;
using LLunsigned long long;
const int M6e35;
const int mo1e97;
LL dp[M][2],cnt[M];
LL qpow(LL a,LL b)
{LL res1;while(b0){if(b1)resres*a%mo;b1;aa*a%mo;}return res;
}
int main()
{int t;scanf(%d,t);while(t--){int n,a,b;scanf(%d%d%d,n,a,b);for(int i1;in;i)dp[i][0]dp[i][1]0;dp[0][0]dp[0][1]1;dp[1][0]5;dp[1][1]21;cnt[1]26;LL paqpow(5,a1),pbqpow(21,b1),res26;// coutpapbendl;for(int i2;in;i){dp[i][0]5*cnt[i-1]%mo;dp[i][1]21*cnt[i-1]%mo;if(ia)dp[i][0](dp[i][0]-dp[i-a-1][1]*pa%momo)%mo;if(ib)dp[i][1](dp[i][1]-dp[i-b-1][0]*pb%momo)%mo;cnt[i](dp[i][0]dp[i][1])%mo;res(cnt[i]res)%mo;}printf(%lld\n,res);}return 0;
}
