题目
题目背景
雨。
用瓢泼已经不足以形容这雨了；水滴密集到近乎在空中连接成固体，视线无法穿透。
四下都是雨落在地上的敲击声——不，已经是轰鸣声——就像天空要将自己撞入大地那样迅猛。
O n e I n D a r k \sf OneInDark OneInDark 往外望去，也只能看到雨。间杂的电闪雷鸣是唯一的光源。
O n e I n D a r k \sf OneInDark OneInDark 坐在孤零零的帐篷里，在这片平原上显得微不足道。
忽而一声惊雷， O n e I n D a r k \sf OneInDark OneInDark 那因恐惧而闭上的双眼再度睁开时，他看到一个巨大的白色身影，立在帐篷前。雨滴似乎不能侵染它半分。
O n e I n D a r k \sf OneInDark OneInDark 知道那是什么。见过它的人，如果还侥幸活着，无一不陷入癫狂。 O n e I n D a r k \sf OneInDark OneInDark 只来得及写下扭曲的 ? ???? ? u γ ?? ? ?? n ?? ν ???? ? \ell_{\!\!\supset}\frak u\gamma\!\imath\;\frak n\;\nu\!\!\jmath ???uγ?nν?，就已经不省人事。
醒时已破晓。 O n e I n D a r k \sf OneInDark OneInDark 看到了他这辈子永远不会忘记的一幕：
雨，兔子，漂浮的蛋。
这是他的话中唯一能够被辨认出的词汇了。
题目描述
你需要选出
n
n
n 个
[
0
,
L
]
[0,L]
[0,L] 中的整数（可以相同），满足最大值
?
β
\geqslant \beta
?β 而次大值
<
α
<\alpha
<α，且最大值小于其他数字的和。额外限制每种数字最多选出
k
k
k 个，请计算有多少种不同的选法。
两种选法不同，当且仅当某种数字的被选中次数不同。答案对 ( 1 0 9 + 7 ) (10^9{+}7) (109+7) 取模。
数据范围与提示
n
?
8
n\leqslant 8
n?8 但
L
?
1
0
9
L\leqslant 10^9
L?109 。保证
1
<
α
?
β
?
L
1<\alpha\leqslant \beta\leqslant L
1<α?β?L 。
思路
名兔名言： n n n 越小，题越难。
好吧我摊牌了其实是我太菜了 😢
先放一个基础做法。大数字的比较，容易想到按二进制位 d p \tt dp dp，就像此题。但怎么让数字有序？怎么统计同一种数字的数量？
我好像忘了 n n n 超级小……可以 3 n ? 2 3^{n-2} 3n?2 记录相邻数字的大小关系（大于或等于或小于），然后用类似插头 d p \tt dp dp 的方式转移。
上面的做法没想到，考虑数学转化。告诫：不要用二元生成函数！真的是维度灾难 😭
坚持一元
还是不敏感 Burnside \text{Burnside} Burnside 定理啊。正是在选择的元素无序时，它才能派上用场啊。只需给置换设定权值 ω ( g ) \omega(g) ω(g) 使得 ω ( G H ) f ( H ) \omega(G_H)f(H) ω(GH?)f(H) 只在 H H H 不含出现次数超过 k k k 的颜色时 = 1 =1 =1 。
设 G H = ? S i c i G_H=\bigoplus S_i^{c_i} GH?=?Sici??，这里的次方指直积，其中 S i S_i Si? 为 i i i 元对称群。不难发现 f ( H ) = ( n ? 1 c 1 , c 2 , … , c n ? 1 ) f(H)={n-1\choose c_1,c_2,\dots,c_{n-1}} f(H)=(c1?,c2?,…,cn?1?n?1?) 。因此我们需要让 ω ( S i ) = i ! ?? ( i ? k ) \omega(S_i)=i!\;(i\leqslant k) ω(Si?)=i!(i?k) 去抵消系数。
我们不妨猜测
ω
(
g
)
=
∏
ν
(
i
)
c
i
\omega(g)=\prod \nu(i)^{c_i}
ω(g)=∏ν(i)ci? 。不难发现只需满足
exp
?
F
(
x
)
=
∑
i
=
0
k
x
i
i
!
\exp F(x)=\sum_{i=0}^{k}\frac{x^i}{i!}
expF(x)=i=0∑k?i!xi?
其中
F
(
x
)
=
∑
i
=
1
+
∞
ν
(
i
)
x
i
i
F(x)=\sum_{i=1}^{+\infty}\frac{\nu(i)x^i}{i}
F(x)=i=1∑+∞?iν(i)xi?
为 ( i ? 1 ) ! ?? ν ( i ) (i{-}1)!\;\nu(i) (i?1)!ν(i) 的 E G F \rm EGF EGF 。用多项式 ln ? \ln ln 可求出 F ( x ) F(x) F(x)，因此也就得到了 ω ( g ) \omega(g) ω(g) 的表达式。
由 Burnside \text{Burnside} Burnside 定理，转而计算 ∑ ω ( g ) ∣ X g ∣ \sum \omega(g)|X^g| ∑ω(g)∣Xg∣ 。显然 g g g 的循环指标可枚举。现在只需计算不动点权值和。
不动点权值
单个数字的选择的
O
G
F
\rm OGF
OGF 为
H
(
x
)
=
1
?
x
α
1
?
x
H(x)=\frac{1-x^\alpha}{1-x}
H(x)=1?x1?xα?，因此循环指标为
∏
x
i
c
i
\prod x_i^{c_i}
∏xici?? 时只需求
∏
H
(
x
i
)
c
i
\prod H(x^i)^{c_i}
∏H(xi)ci? 。这很容易计算：暴力求出分母
M
(
x
)
=
∏
i
=
1
n
?
1
(
1
?
x
i
)
c
i
M(x)=\prod_{i=1}^{n-1}(1-x^i)^{c_i}
M(x)=i=1∏n?1?(1?xi)ci?
后，分子就是 M ( x α ) M(x^\alpha) M(xα) 。
最终贡献中，
[
x
t
]
M
(
x
α
)
M
(
x
)
??
(
t
>
β
)
[x^t]\frac{M(x^\alpha)}{M(x)}\;(t>\beta)
[xt]M(x)M(xα)?(t>β) 的系数是
(
min
?
{
L
+
1
,
t
}
?
β
)
(\min\{L{+}1,t\}{-}\beta)
(min{L+1,t}?β) 。那么事实上就是
(
L
+
1
?
β
)
?
[
x
+
∞
]
M
(
x
α
)
(
1
?
x
)
M
(
x
)
?
(
L
+
1
)
?
[
x
L
+
1
]
M
(
x
α
)
(
1
?
x
)
M
(
x
)
+
[
x
L
]
1
1
?
x
[
M
(
x
α
)
M
(
x
)
]
′
?
[
x
β
]
x
1
?
x
[
M
(
x
α
)
M
(
x
)
]
′
+
β
?
[
x
β
]
M
(
x
α
)
(
1
?
x
)
M
(
x
)
\begin{aligned} &\quad(L{+}1{-}\beta)\cdot[x^{+\infty}]\frac{M(x^\alpha)}{(1{-}x)M(x)}\\ &-(L{+}1)\cdot[x^{L+1}]\frac{M(x^\alpha)}{(1{-}x)M(x)}\\ &+[x^L]\frac{1}{1{-}x}\left[\frac{M(x^\alpha)}{M(x)}\right]'\\ &-[x^\beta]\frac{x}{1{-}x}\left[M(x^\alpha)\over M(x)\right]'\\ &+\beta\cdot[x^\beta]\frac{M(x^\alpha)}{(1{-}x)M(x)} \end{aligned}
?(L+1?β)?[x+∞](1?x)M(x)M(xα)??(L+1)?[xL+1](1?x)M(x)M(xα)?+[xL]1?x1?[M(x)M(xα)?]′?[xβ]1?xx?[M(x)M(xα)?]′+β?[xβ](1?x)M(x)M(xα)??
不涉及求导的项，就是求 M ( x α ) ( 1 ? x ) M ( x ) \frac{M(x^\alpha)}{(1-x)M(x)} (1?x)M(x)M(xα)? 的远处值。注意到 deg ? M ( x ) = n ? 1 \deg M(x)=n{-}1 degM(x)=n?1，暴力枚举分子的每一项，剩下的问题就是 1 γ ( x ) \frac{1}{\gamma(x)} γ(x)1? 的远处值，显然就是个线性递推。总时间复杂度 O ( n P ( n ) log ? L ) \mathcal O(n\mathcal P(n)\log L) O(nP(n)logL)，其中 P ( n ) \mathcal P(n) P(n) 是多项式乘法的复杂度。
涉及求导的项则是
1
1
?
x
[
M
(
x
α
)
M
(
x
)
]
′
\frac{1}{1-x}\left[{M(x^\alpha)\over M(x)}\right]'
1?x1?[M(x)M(xα)?]′ 的远处值。要么分子求导，这可以和上面一样通过暴力枚举每一项得到；要么分母求导，我们将得到
?
M
(
x
α
)
M
′
(
x
)
(
1
?
x
)
M
(
x
)
2
\frac{-M(x^\alpha)M'(x)}{(1{-}x)M(x)^2}
(1?x)M(x)2?M(xα)M′(x)?
这看上去略显复杂。我们不妨找到其真正的样子
?
M
′
(
x
)
M
(
x
)
=
∑
i
=
1
n
?
1
i
c
i
x
i
?
1
1
?
x
i
\frac{-M'(x)}{M(x)}=\sum_{i=1}^{n-1}\frac{ic_ix^{i-1}}{1{-}x^i}
M(x)?M′(x)?=i=1∑n?1?1?xiici?xi?1?
由于
∑
i
c
i
=
n
?
1
\sum ic_i=n{-}1
∑ici?=n?1，不同的
i
i
i 只有
n
\sqrt{n}
n? 个。就本题的数据范围而言，这有意义吗。枚举之，再做线性递推。总复杂度
O
(
n
1.5
P
(
n
)
log
?
L
)
\mathcal O(n^{1.5}\mathcal P(n)\log L)
O(n1.5P(n)logL) 。
上述过程是对某个确定的 g g g 的循环指标的求解，因此最终复杂度为 O ( Partition ( n ) ? n 1.5 P ( n ) log ? L ) \mathcal O(\text{Partition}(n)\cdot n^{1.5}\mathcal P(n)\log L) O(Partition(n)?n1.5P(n)logL) 。
代码
极限数据只需 11 m s 11\rm ms 11ms 出结果，恐怖如斯。
建议使用 vector 实现 Polynomial 类，不然真的很难写。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <initializer_list>
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
for(; isdigit(c); c=getchar()) a = a*10+(c^48);
return a*f;
}
const int MOD = 1e9+7;
inline llong qkpow(llong b, int q){
llong a = 1;
for(; q; q>>=1,b=b*b%MOD) if(q&1) a = a*b%MOD;
return a;
}
struct Poly : public std::vector<int>{
Poly(){ clear(); }
Poly(std::initializer_list<int> args){
std::initializer_list<int>::iterator it;
for(it=args.begin(); it!=args.end(); ++it)
emplace_back(*it); // just push
}
Poly getInv() const {
assert(at(0) == 1);
unsigned len = size(); int v = 0;
Poly c; c.resize(len); c[0] = 1;
for(unsigned i=1; i!=len; ++i,v=0){
for(unsigned j=0; j!=i; ++j)
v = int((v+llong(c[j])*at(i-j))%MOD);
c[i] = v ? MOD-v : 0;
}
return c;
}
Poly getLn() const;
Poly deri() const { // derivative
unsigned len = size();
Poly c; c.resize(len-1);
for(unsigned i=1; i!=len; ++i)
c[i-1] = int(llong(i)*at(i)%MOD);
return c;
}
Poly inte() const { // integral
unsigned len = size();
Poly c; c.resize(len+1);
for(unsigned i=1; i<=len; ++i)
c[i] = int(qkpow(i,MOD-2)*at(i-1)%MOD);
c[0] = 0; return c;
}
Poly extract_even() const {
unsigned len = size();
Poly c; c.resize((len+1)>>1);
for(unsigned i=0; i<len; i+=2) c[i>>1] = at(i);
return c;
}
Poly extract_odd() const {
unsigned len = size();
Poly c; c.resize(len>>1);
for(unsigned i=1; i<len; i+=2) c[i>>1] = at(i);
return c;
}
int at_far(int) const ;
};
Poly operator * (const Poly &a, const Poly &b){
unsigned lena = a.size(), lenb = b.size();
Poly c; c.resize(lena+lenb-1u, 0);
for(unsigned i=0; i!=lena; ++i)
for(unsigned j=0; j!=lenb; ++j)
c[i+j] = int((c[i+j]+llong(a[i])*b[j])%MOD);
return c;
}
Poly Poly::getLn() const {
Poly res = (deri()*getInv()).inte();
res.resize(size()); return res;
}
int Poly::at_far(int L) const {
if(L < 0) return 0;
Poly son; son.resize(1,1);
for(Poly mom=*this; L; L>>=1){
Poly nxt = mom; unsigned len = mom.size();
for(unsigned i=1; i<len; i+=2)
if(nxt[i]) nxt[i] = MOD-nxt[i];
mom = (mom*nxt).extract_even(), son = son*nxt;
if(L&1) son = son.extract_odd();
else son = son.extract_even();
}
return son[0];
}
const int MAXN = 9;
int alpha, beta, L, chose[MAXN];
int at_far(const Poly &son, const Poly &mom, const int &n){
unsigned len = std::min(son.size(),
std::vector<int>::size_type(n/alpha)+1);
int res = 0;
for(unsigned i=0; i!=len; ++i)
res = int((res+llong(son[i])*
mom.at_far(n-alpha*i))%MOD);
return res;
}
int check(const int &n){
static Poly son; son.clear();
son.resize(n+1,0), son[0] = 1;
int res = L+1-beta;
rep(t,1,n) rep(_,1,chose[t]){
drep(i,n,t) son[i] = int((son[i]+MOD-son[i-t])%MOD);
res = int(llong(res)*alpha%MOD);
}
Poly mom = son*Poly{1,MOD-1}; // (1-x)
const unsigned len = son.size();
for(unsigned i=0; i!=len; ++i){
if(i > (L+1)/alpha) break; // too big
res = int((res+llong(MOD-L-1)*son[i]
%MOD*mom.at_far(L+1-alpha*i))%MOD); // -(L+1)[]
res = int((res+llong(alpha*i)*son[i]
%MOD*mom.at_far(L-alpha*i+1))%MOD); // +[]'
res = int((res+llong(MOD-alpha*i)*son[i]
%MOD*mom.at_far(beta-alpha*i))%MOD); // -[]'
res = int((res+llong(beta)*son[i]
%MOD*mom.at_far(beta-i*alpha))%MOD); // +b[]
}
rep(t,1,n) if(chose[t]){
Poly nxt; nxt.resize(t+1, 0);
nxt[0] = 1, nxt[t] = MOD-1;
nxt = nxt*mom; // new fraction mother
res = int((res+llong(t*chose[t])
*at_far(son,nxt,L-t+1))%MOD); // +[]'
res = int((res+llong(MOD-t*chose[t])
*at_far(son,nxt,beta-t))%MOD); // -[]'
}
return res;
}
Poly coe; int ans, invjc[MAXN];
// @param n how many elements chosen
void dfs(const int &n, int t, int left, int omega){
if(t == 1){
chose[1] = left; // must use up
ans = int((ans+llong(check(n))
*omega%MOD*invjc[left])%MOD); return;
}
for(chose[t]=0; left>=0; left-=t,++chose[t]){
dfs(n,t-1,left,int(omega // unordered
*llong(invjc[chose[t]])%MOD));
omega = int(llong(coe[t])*omega%MOD);
}
}
int main(){
int n = readint(); L = readint();
beta = readint(), alpha = readint()+1;
int maxcnt = readint();
if(maxcnt == n) maxcnt = n-1;
rep(i,invjc[0]=1,n) invjc[i] = int(
qkpow(i,MOD-2)*invjc[i-1]%MOD);
coe.resize(maxcnt+1,1);
coe.resize(n,0); // pre-compute
coe = coe.getLn(); // long enough
dfs(n-1, n-1, n-1, 1);
printf("%d\n",ans);
return 0;
}
