直接上题了，前言今天就省了，，，，
题目：
HDUOJ 6092 Rikka with Subset
（看的懂英语的尽量看英语，毕竟全文翻译没有那么准确）
题目大意：给你一个未知的a[]数组，长度为m+1，再给你一个b[]数组，长度也为m+1，表示以所有各个集合分别的和（包括空集）为下标个数为数值，n为集合的最大值，让求出a[]数组。
样例解释：
第一组样例：
a[]:1 2
b[]:1 1 1 1
n:2
m:3
集合
（下标）和：0 1 2 3 4
（b[]子集合）[ ][1,1][1,2][2,2]
PE提醒：输出结尾没有空格
题解：
一种动态维护的思想，还有听说这是01背包的方案数的求值，就是说把a[]数组中的每一个数看做一个物品，只需要去求出物品中的个数，所以转移方程就是这样：
f[j][k]=f[j-1][k]+f[j-1][k-i];（i对于第j个数刚好兑换成k时的方案贡献k>=i）
优化过后（滚动数组优化）：
f[k]=f[k]+f[k-i];（k:m—i）（0~i-1刚好兑换成k时的方案贡献k>=i）（所以此时k最多就是1到m就是104）
关于上面的i可以这样讲，由于是字典序，这道题的下标是a[i]，然而值就是i了。
有关FFT、NTT的解法请参考dalao博客： 传送门
AC代码：
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e4+7;
const int stream=60;
int t,tt,n,m,a[sea],b[sea];
int f[sea];
int main()
{
t=read();while(t--) {
memset(f,0,sizeof(f)); int tt=0;n=read(); m=read();for(int i=0;i<=m;i++) b[i]=read();//m+1个f[0]=1;//赋初值提醒for(int i=1;i<=m;i++){
if(!b[i]) continue;if(tt==n) break;//两个剪枝，优化int temp=b[i]-f[i];//b[i]中的i的个数减去之前i-1加起来所有的和就是i的个数（因为1～k-1个数确定后，能凑到和为k的种数，不够的说明a序列中有b[k]-bb[k]个数的k）（这也就有点动态维护的意思了）for(int j=0;j<temp;j++) {
a[tt++]=i;//加入a[]数组中for(int k=m;k>=i;k--)//反着来，避免已经加到结果里的数字再加一遍，这里有01背包的感觉f[k]+=f[k-i];//（像一个前缀和的东西）进行对f[]的修改}} printf("%d",a[0]);for(int i=1;i<tt;i++)printf(" %d",a[i]);//PE提醒printf("\n");}return 0;
}
//f[j][k]=f[j-1][k]+f[j-1][k-i];
//f[k]=f[k]+f[k-i];
//FFT/NTT/完全背包/多重背包好像都能写
这可能是我有史以来最全的单题题解了吧，，，，