https://codeforces.com/gym/101669
即使DP式子再短，我还是想不到.jpg 这题关键想到是要枚举空位，f[i]为前i中的所有球已经放好了，且第i个为空格的方案数是多少
设s[i]为前i位的球的数量，那么前i位的空格总数就是i-s[i]了
由于M<=N，我们把n++，保证在n+1的位置处至少有一个空格，在那里统计算出答案。
只有每次s[i]==s[i-1]的时候，说明这里没有球直接下落，他可以作为一个空位，只有i-1-s[i-1]>=0时，f[i]才能有一个空位赋值为g[i-1-s[i-1]],g[i]表示之前已经有了i个空位的方案数，由于前i-1位已经有了g[i-1-s[i-1]]个空位了，自然吧方案数赋值给他。
否则如果不能为空位，那么f[i]=0
由于此时i多了一个空格，那么g[i-s[i]]也多处了f[i]种方案，加上就行了
看了看咖啡鸡和夜幕的另一种解法是维护一个offset偏移量+i-s[i]存在dp数组中，表示到i位置多了多少空格或者欠了多少空格的方案数，这样也是可以的
#include<bits/stdc++.h> using namespace std; const int maxl=1e6+10; const int mod=1e9+7; int n,m; int s[maxl],f[maxl],g[maxl]; inline void prework() { scanf("%d%d",&n,&m); ++n;int x; for(int i=1;i<=m;i++) { scanf("%d",&x); s[x]++; } for(int i=1;i<=n;i++) s[i]+=s[i-1]; } inline void mainwork() { g[0]=1; for(int i=1;i<=n;i++) if(s[i]==s[i-1]) { if(i-1-s[i-1]>=0) { f[i]=g[i-1-s[i-1]]; g[i-s[i]]=(g[i-s[i]]+f[i])%mod; } } } inline void print() { printf("%d",f[n]); } int main() { prework(); mainwork(); print(); return 0; }
