题目链接 emmm 总感觉哪里做过 但是又没有记录 大概是遇到过 鸽掉了 给了我们n1 n2 k1 k2 排列一个队形，人数n1+n2 n1种人不能连续排k1个 同理n2 问方案数
emmm 想了下 好像没啥想法 那就继续想(于是20分钟过去了) 我们定义dp[i][j][1/2] 选取i个n1的人 j个n2的人 组成一个排列以n1/ n2结尾的队伍 那么我们枚举当前可以连续排列的数，min(i,k1) min(j,k2) 于是dp[i][j][1] =dp[i][j][1]+dp[i-len][j][2] %mods 同理dp[i][j][2] 因为此时你是以1/2结尾的 那么上一个状态就是2/1 于是每次推过去就OK 初始化一下
dp有思路就是大水题
#include<bits/stdc++.h> #include<stdlib.h> #include<algorithm> #include<stdio.h> #include<string.h> #include<queue> #include<time.h> #include <cstdio> #include <iostream> #include <vector> #define ll long long #define int long long #define inf 0x3f3f3f3f #define mods 100000000 #define modd 998244353 #define PI acos(-1) #define fi first #define se second #define lowbit(x) (x&(-x)) #define mp make_pair #define pb push_back #define si size() #define E exp(1.0) #define fixed cout.setf(ios::fixed) #define fixeds(x) setprecision(x) #define IOS ios::sync_with_stdio(false);cin.tie(0) using namespace std; ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);} template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂% ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元 (分子*qp(分母,mod-2,mod))%mod; ll dp[500][500][3]; signed main(){ ll n1,n2,k1,k2; read(n1); read(n2); read(k1); read(k2); for(int i=1;i<=k1;i++){ dp[i][0][1]=1;// 直接排列一样的 } for(int i=1;i<=k2;i++){ dp[0][i][2]=1;// 直接排列一样的 } // dp[i][j][?] 拿i个n1的 拿j个n2的组成以? 结尾的排列数 for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;j++){ ll len1=min(i,k1);//连续尾巴 ll len2=min(j,k2);// for(int k=1;k<=len1;k++){ dp[i][j][1]=(dp[i][j][1]+dp[i-k][j][2])%mods; } for(int k=1;k<=len2;k++){ dp[i][j][2]=(dp[i][j][2]+dp[i][j-k][1])%mods; } } } printf("%lld\n",(dp[n1][n2][1]+dp[n1][n2][2])%mods); }