奇异序列
描述 有一个长度为n的自然序列。定义一个序列为“奇异k序列”当且仅当选一个子序（不要求连续）的和为k
现在，但是L忘了给你的序列{ai}具体是什么了，只知道每个ai是满足0≤ai≤l的整数,请你计算有多少种可能是“奇异k序列”
输入 一行三个正整数 n,k,l。
输出 一行一个正整数表示答案模 998244353 的值
样例输入 [复制] 2 2 2 样例输出 [复制] 6
题解： 装压背包。f[i][j]代表到第i个数凑j状态的方案数。由于j很小，所以状态压缩
#include<bits/stdc++.h> using namespace std; #define int long long const int mod=998244353; inline int read() { int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return data*w; } int n,k,l; int dp[21][1<<20|1]; int mx,lim=100001; int rm; int ans=0; signed main(){ n=read();k=read();l=read(); mx=(1<<k)-1;rm=max((l-k),0ll); rm++; lim=min(k,l); dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=mx;j++){ if(dp[i-1][j]){ for(int kk=1;kk<=lim;kk++){ dp[i][(j|(j<<kk)|(1<<(kk-1)))&mx]=(dp[i][(j|(j<<kk)|(1<<(kk-1)))&mx]+dp[i-1][j]%mod)%mod; } dp[i][j]=(dp[i][j]+dp[i-1][j]*rm%mod+mod)%mod; } } } for(int j=1<<(k-1);j<=mx;j++) ans=(ans+dp[n][j])%mod; printf("%lld",ans); return 0; }