UOJ #567. 【IOI2020】Biscuits

题面传送门
考虑一个\(y\)值能被弄出来的条件。
我们发现实际算的时候只有小的位会去凑大的位，而大的位不会跑上去凑小的位。
所以可以考虑每一个后缀，容易发现对于每个后缀来说，已经有的biscuits总和一定要大于等于\(y\)中这些后缀的总和。
容易发现这是充要条件，然后就变成了每个后缀不能大于某个数的dp问题。
设\(dp_{i,S}\)为第\(i\)位，不能大于\(S\)的方案数，直接记搜就能过。
？为什么这个看上去复杂度假的离谱的东西都能过？
实际上状态数是\(O(k^2)\)的，因为\(S\)只能是\(k\)个限制中的一个，而不同的\(i\)是\(O(k)\)的所以是\(O(k^2)\)
总复杂度\(O(Tk^2\log k)\)轻松跑过。
code:

#include "biscuits.h"

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (60+5)
#define M (1000000+5)
#define K (20+5)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n=60;ll A[N],P[N],W[N];map F[N];
I ll dfs(int x,ll ToT){
	if(x==-1) return 1;ToT=min(ToT&((1ll<>x&1) return F[x][ToT]=dfs(x-1,(1ll< a){
	int i;Me(A,0);for(i=0;i