題目連結
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);
}