好题实吹 这种排列计数问题确实感觉无从下手啊
考虑暴力，是枚举每一个排列，排列的贡献为C(L-W,n)，其中W是max(di-1,di)-1，即相邻两个魔法师之间不能放的位置
考虑到攻击范围比较小，一个人最多打80个位置，假如能够计算出对于每个W的排列方案数，就能算出答案了
排序消掉max，按大到小插入魔法师，那么对于当前魔法师，就有三种情况：
1、自己找个地方随便放，那么最后它对不能够放的位置的贡献就是2*(di-1)
2、放在其中一个魔法师旁边，贡献为di-1
3、放在两个魔法师之间，贡献为0
但是直接这样算方案的话，插入的魔法师会分成很多段，状态就很难表示了
考虑到我们并不关心魔法师具体的位置或者相对位置，只关心他打了多少位置
我们再弄一个关键，目前还剩下的空位
什么鬼？就是每次插入魔法师的时候，先想好未来让不让一个魔法师放到自己的左/右边，因为不关心位置所以位置可以直接+0,+1,或+2，当然插入进来也会用1个位置
这样就可以DP了，设f[i][j][k]表示前i个人，有多少位置可以插入，当前能打多少位置
注意假如+1，方案数要乘2，因为可以放左也可以放右
我预处理阶乘的逆元比较蠢，每个都求了一次，实际上把最后一个算出来不断往前乘就好了
upd:这里给出另一种做法，或许更好理解些
前面的都一样，到分成很多段那儿，我们可以设分成了多少段
设f[i][j][k][p]表示前i个人，分成了j段，能打了k个位置，p=0/1/2意思是左界和右界共到了多少个
思路是把两段合并，还是接在一段一边，还是插在某两段中间不相连
#include#include #include #include #include #include using namespace std;typedef long long LL;const int _=1e2;const int maxn=40+10;const int maxd=40+10;const int maxL=1e6+_;const LL mod=1e9+7;LL quick_pow(LL A,LL p){ LL ret=1; while(p!=0) { if(p%2==1)ret=ret*A%mod; A=A*A%mod;p/=2; } return ret;}LL fac[maxL],fac_inv[maxL];void yu(int L){ fac[0]=1,fac_inv[0]=1; for(int i=1;i<=L;i++) fac[i]=fac[i-1]*i%mod,fac_inv[i]=quick_pow(fac[i],mod-2);}LL C(int n,int m){ return fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;}int d[maxn];LL f[maxn][maxn][2*maxn*maxd];int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); int L,n,li=0; scanf("%d%d",&L,&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]),d[i]--,li+=2*d[i]; sort(d+1,d+n+1); reverse(d+1,d+n+1); f[0][1][0]=1; for(int i=0;i
#include#include #include #include #include #include using namespace std;typedef long long LL;const int _=1e2;const int maxn=40+10;const int maxd=40+10;const int maxL=1e6+_;const LL mod=1e9+7;LL quick_pow(LL A,LL p){ LL ret=1; while(p!=0) { if(p%2==1)ret=ret*A%mod; A=A*A%mod;p/=2; } return ret;}LL fac[maxL],fac_inv[maxL];void yu(int L){ fac[0]=1,fac_inv[0]=1; for(int i=1;i<=L;i++) fac[i]=fac[i-1]*i%mod,fac_inv[i]=quick_pow(fac[i],mod-2);}LL C(int n,int m){ return fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;}int d[maxn];LL f[2][maxn][2*maxn*maxd][3];//枚举到第i个位置，有j段，覆盖长度为k，其中挨了多少边界int main(){// freopen("a.in","r",stdin);// freopen("a.out","w",stdout); int L,n,li=0; scanf("%d%d",&L,&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]),d[i]--,li+=2*d[i]; sort(d+1,d+n+1); reverse(d+1,d+n+1); int now=0; f[now][1][2*d[1]][0]=1; f[now][1][d[1]][1]=2; for(int i=1;i