(mathcal{Description})
Link.
破案了，朝鲜时蔬 = 超现实树！（指写得像那什么一样的题面。
对于整数集 (X)，定义其 好子集 为满足 (Ysubseteq Xlandleft(sum_{yin Y}y ight)midleft(sum_{xin X}x ight)) 的任意 (Y)。求 (S_n=[1,n]capmathbb N) 的所有 (m) 阶子集中，包含 (k) 阶 好子集 数量最多的子集数。答案模 ((10^9+7))。
(kle mle nle10^{12})，(mle4)。
(mathcal{Solution})
[mathfrak{ ext{Defining }LaTeX ext{ macros...}}
ewcommand{vct}[1]{oldsymbol{#1}}
ewcommand{stir}[2]{genfrac{{}{}}{0pt}{}{#1}{#2}}
ewcommand{opn}[1]{operatorname{#1}}
ewcommand{lcm}[0]{opn{lcm}}
ewcommand{sg}[0]{opn{sg}}
ewcommand{dist}[0]{opn{dist}}
ewcommand{lca}[0]{opn{lca}}
ewcommand{floor}[2]{leftlfloorfrac{#1}{#2}
ight
floor}
ewcommand{ceil}[2]{leftlceilfrac{#1}{#2}
ight
ceil}
]
令 (f_{m,k}(n)) 表示一组 ((m,k,n)) 的答案，讨论之。
-
(m=k=1.)
显然 (f_{m,k}(n)=n)。
-
(m=2,k=1.)
设子集为 ({a,b})，(a<b)，则应有 (amid b)。所以 (f_{m,k}(n)=sum_{i=1}^nleft(floor{n}{i}-1 ight))。
-
(m=k=2.)
显然 (f_{m,k}(n)=inom{n}{2})。
-
(m=3,k=1.)
必然有 ({k,2k,3k}) 为最优集合，即 (f_{m,k}(n)=floor{n}{3})。
证明
- 考虑集合 ${x,y,z}$，$x -
(m=3,k=2.)
设子集 ({a,b,c})，(a<b<c)，则应有 ((a+b)mid c)。枚举 (a+b=i)，得到
[f_{m,k}(n)=sum_{i=1}^nfloor{i-1}{2}floor{n}{i}. ] -
(m=k=3.)
显然 (f_{m,k}(n)=inom{n}{3})。
-
(m=4,k=1.)
这个结论不太好正向推出啊。总之，当 (nge6)，最优集合 ({a,b,c,d}) 的形式必为以下一种：
[{k,2k,3k,4k},\{k,2k,6k,9k},\{k,3k,8k,12k},\{k,4k,5k,10k},\{k,6k,14k,21k},\{2k,3k,10k,15k}. ]加之边界讨论，最终有
[f_{m,k}=egin{cases}1,&nle5\floor{n}{6}+floor{n}{9}+floor{n}{10}+floor{n}{12}+floor{n}{15}+floor{n}{21},&n>5end{cases}. ]证明
对于最优的 ${a,b,c,d}$，$a -
(m=4,k=2.)
(n<11) 可以打表，(nge11) 我们喜闻乐见地得到神奇结论：
[f_{m,k}(n)=floor{n}{11}+floor{n}{29},~~~~nge11. ]证明
构造最优的 ${a,b,c,d}$，应有 $$ egin{cases} (a+b)mid(a+b+c+d)Rightarrow (a+b)mid(c+d),\ (a+c)mid(a+b+c+d)Rightarrow (a+c)mid(b+d),\ left.egin{array}{} (a+d)mid(a+b+c+d)\ (b+c)mid(a+b+c+d) end{array} ight}Rightarrow a+b=c+d. end{cases} $$ 设 $k(a+c)=b+d=a+2b-c<3(a+c)$，知 $k=2$。类似讨论可证。 $square$ -
(m=4,k=3.)
这个总算能阳间推导了 qwq。
对于 ({a,b,c,d})，必然 ((a+b+c)mid d)。枚举 (a+b+c=i)，记 (f(i)) 表示把 (i) 拆成 (a,b,c) 的方案数，不难发现
[f(i)=inom{i-1}{2}-3left(ceil{n}{2}-1 ight)+2[3mid n]. ]答案则为
[f_{m,k}(n)=sum_{i=1}^nf(n)floor{n}{i}. ]整除分块即可。
-
(m=k=4.)
显然 (f_{m,k}(n)=inom{n}{4})。
放三道傻瓜题的原因是让选手享受这题一个情况 (10) 分的快乐吗？（
(mathcal{Code})
/*~Rainybunny~*/
// Have you MODULED correctly?
#ifndef RYBY
#pragma GCC optimize( "Ofast" )
#endif
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
typedef long long LL;
const int MOD = 1e9 + 7, INV2 = 500000004, INV3 = 333333336, INV4 = 250000002;
LL n;
int m, k;
inline LL sqrs( const LL x ) {
return x % MOD * ( ( x + 1 ) % MOD ) % MOD * ( ( 2 * x + 1 ) % MOD ) % MOD
* INV2 % MOD * INV3 % MOD;
}
inline void solve11() {
printf( "%lld
", n % MOD );
}
inline void solve21() {
LL ans = 0;
for ( LL l = 1, r; l <= n; l = r + 1 ) {
r = n / ( n / l );
ans = ( ans + ( r - l + 1 ) % MOD
* ( ( n / l - 1 ) % MOD ) % MOD ) % MOD;
}
printf( "%lld
", ans );
}
inline void solve22() {
printf( "%lld
", n % MOD * ( ( n - 1 ) % MOD ) % MOD * INV2 % MOD );
}
inline void solve31() {
printf( "%lld
", n / 3 % MOD );
}
inline void solve32() {
LL ans = 0;
for ( LL l = 1, r; l <= n; l = r + 1 ) {
r = n / ( n / l );
if ( l + ( l & 1 ) <= r - ( r & 1 ) ) { // even.
LL s = l + ( l & 1 ) - 1 >> 1, t = r - ( r & 1 ) - 1 >> 1;
LL c = ( r - ( r & 1 ) - ( l + ( l & 1 ) ) >> 1 ) + 1;
ans = ( ans + n / l % MOD * ( ( s + t ) % MOD ) % MOD
* ( c % MOD ) % MOD * INV2 % MOD ) % MOD;
}
if ( l + !( l & 1 ) <= r - !( r & 1 ) ) { // odd.
LL s = l + !( l & 1 ) - 1 >> 1, t = r - !( r & 1 ) - 1 >> 1;
LL c = ( r - !( r & 1 ) - ( l + !( l & 1 ) ) >> 1 ) + 1;
ans = ( ans + n / l % MOD * ( ( s + t ) % MOD ) % MOD
* ( c % MOD ) % MOD * INV2 % MOD ) % MOD;
}
}
printf( "%lld
", ans );
}
inline void solve33() {
printf( "%lld
", n % MOD * ( ( n - 1 ) % MOD ) % MOD
* ( ( n - 2 ) % MOD ) % MOD * INV2 % MOD * INV3 % MOD );
}
inline void solve41() {
if ( n <= 5 ) return void( puts( "1" ) );
printf( "%lld
", ( n / 6 + n / 9 + n / 10
+ n / 12 + n / 15 + n / 21 ) % MOD );
}
inline void solve42() {
static const int SMA[] = { 1, 1, 1, 3, 6, 9, 10 };
if ( n <= 10 ) return void( printf( "%d
", SMA[n - 4] ) );
printf( "%lld
", ( ( n / 11 ) + ( n / 29 ) ) % MOD );
}
inline void solve43() {
if ( n == 4 ) return void( puts( "1" ) );
if ( n == 5 ) return void( printf( "%lld
", n % MOD ) );
LL ans = 0; // (-MOD,MOD) !!!
for ( LL l = 6, r; l <= n; l = r + 1 ) {
r = n / ( n / l );
LL a = ( sqrs( r - 1 ) - sqrs( l - 2 ) ) % MOD;
LL b = ( l + r - 2 ) % MOD
* ( ( r - l + 1 ) % MOD ) % MOD * INV2 % MOD;
LL c = 0;
if ( l + ( l & 1 ) <= r - ( r & 1 ) ) { // even.
LL s = l + ( l & 1 ) >> 1, t = r - ( r & 1 ) >> 1;
LL k = ( r - ( r & 1 ) - ( l + ( l & 1 ) ) >> 1 ) + 1;
c = ( c + ( s + t ) % MOD * ( k % MOD ) % MOD * INV2 % MOD ) % MOD;
}
if ( l + !( l & 1 ) <= r - !( r & 1 ) ) { // odd.
LL s = l + !( l & 1 ) + 1 >> 1, t = r - !( r & 1 ) + 1 >> 1;
LL k = ( r - !( r & 1 ) - ( l + !( l & 1 ) ) >> 1 ) + 1;
c = ( c + ( s + t ) % MOD * ( k % MOD ) % MOD * INV2 % MOD ) % MOD;
}
ans = ( ans + ( n / l ) % MOD * ( ( a - b ) % MOD * INV2 % MOD
- ( 3 * c ) % MOD + 3 * ( r - l + 1 ) % MOD
+ 2 * ( r / 3 - ( l - 1 ) / 3 ) % MOD ) % MOD
* INV2 % MOD * INV3 % MOD ) % MOD;
}
printf( "%lld
", ( ans % MOD + MOD ) % MOD );
}
inline void solve44() {
printf( "%lld
", n % MOD * ( ( n - 1 ) % MOD ) % MOD
* ( ( n - 2 ) % MOD ) % MOD * ( ( n - 3 ) % MOD ) % MOD
* INV2 % MOD * INV3 % MOD * INV4 % MOD );
}
int main() {
freopen( "vegetable.in", "r", stdin );
freopen( "vegetable.out", "w", stdout );
scanf( "%lld %d %d", &n, &m, &k );
if ( m == 1 ) return solve11(), 0;
if ( m == 2 ) {
if ( k == 1 ) return solve21(), 0;
if ( k == 2 ) return solve22(), 0;
}
if ( m == 3 ) {
if ( k == 1 ) return solve31(), 0;
if ( k == 2 ) return solve32(), 0;
if ( k == 3 ) return solve33(), 0;
}
if ( m == 4 ) {
if ( k == 1 ) return solve41(), 0;
if ( k == 2 ) return solve42(), 0;
if ( k == 3 ) return solve43(), 0;
if ( k == 4 ) return solve44(), 0;
}
return 0;
}