decription

对于一个有穷非空正整数集合S={x1,x2,x3,...,xn}⊂N+(n≥1)S=\{x_1,x_2,x_3,...,x_n\}\subset N^+(n\ge 1)S={x1​,x2​,x3​,...,xn​}⊂N+(n≥1)，定义其和$sum(S)$为所有元素的和

• $sum(S)=x_1+...+x_n$

定义其$m(1\le m\le n)$阶子集集合${\mathfrak{S}}_m(S)$为其所有$m$阶子集的集合

• Sm(S)={T∣T={y1,…,ym}⊆S}\mathfrak{S}_m(S)=\Big\{T\Big|T=\{y_1,\dots,y_m\}\subseteq S\Big\}Sm​(S)={T∣∣∣​T={y1​,…,ym​}⊆S}

$T$就是从$S$中选$m$个不同数的组成的一个子集，${\mathfrak{S}}_m(S)$就是子集$T$所有情况的集合

定义其$k(1\le k\le n)$级价值子集集${\mathfrak{T}}_k(S)$为其所有$k$阶子集中和整除$sum(S)$的

• ${\mathfrak{T}}_k(S)=\left\{T\right|k=\frac{sum(S)}{sum(T)}\wedge k\in N^{+}\}\bigcap {\mathfrak{S}}_k(S)$

就是满足上一个要求的基础上，子集元素和能整除原来的大集合的子集的集合

定义其$m(1\le m\le n)$阶$k(1\le k\le m)$级价值函数为其所有$m$阶子集中$k$级价值子集集的阶的最大值

• $f_{m,k}(S)=\max \{|{\mathfrak{T}}_k(T)||T\in {\mathfrak{S}}_m(S)\}$

定义其$m(1\le m\le n)$阶$k(1\le k\le m)$级价值函数的值点集合${\mathfrak{P}}_{m,k}(S)$为取到上述最大值的$m$阶子集的集合

• ${\mathfrak{P}}_{m,k}(S)=\left\{T\right||{\mathfrak{T}}_k(T)|=f_{m,k}(S)\}\bigcap {\mathfrak{S}}_m(S)$

给出$n,m,k$，表示集合$S=1,2,...,n$

求$|{\mathfrak{P}}_{m,k}(S)|$，即有多少个$m$阶子集能取到最大值，答案对$10^9+7$取模

$1\le n\le 10^{12}$

子任务编号	分值	m=	k=
1	10	1	1
2	10	2	1
3	10	2	2
4	10	3	1
5	10	3	2
6	10	3	3
7	10	4	1
8	10	4	2
9	10	4	3
10	10	4	4

solution

这种分数据点写不同算法的题真的很不错，如果不那么绕弯子就更好了！

有些点直接写吐了，giao

实际上，上面的四种定义，从后往前看其实很像递归的感觉，而我们就需要在这种递归思想中找到答案的规律！（证明也行)

倒着看，实际上是最开始的集合S={1,2,...,n}S=\{1,2,...,n\}S={1,2,...,n}，从中选$m$个定义为子集T={x1,...,xm}T=\{x_1,...,x_m\}T={x1​,...,xm​}，再从$T$中选$k$个定义为子子集$P$

---

m=k

显然只要从$S$中选出$m$个后，$T$中选$k$个组成的$P$，一定满足$sum(T)=sum(P)$

所以答案就是从$n$个中选$m$个的方案数
$$C(n,m)$$

void subtask1() {int ans = 1;for( int i = n;i > n - m;i -- )ans = i % mod * ans % mod;for( int i = 1;i <= m;i ++ )ans = ans * qkpow( i, mod - 2 ) % mod;printf( "%lld\n", ans );
}

---

m=2,k=1

不妨假设正整数$x_1<x_2$

由于$x_2\nmid x_1\Rightarrow x_2\nmid (x_1+x_2)$，（显然较大值不会是较小值的因数，不可能整除）

所以只可能有$x_1\mid x_2\Rightarrow x_1\mid (x_1+x_2)$

枚举$x_1=i$，则$x_2=k\ast i,k\in [2,\lfloor \frac{n}{i}\rfloor ]$，即有$\lfloor \frac{n}{i}\rfloor -2+1=\lfloor \frac{n}{i}\rfloor -1$

答案为$$\sum _{i=1}^n(\lfloor \frac{n}{i}\rfloor -1)$$
按照$\lfloor \frac{n}{i}\rfloor$分块，连续一段区间$[l,r]$的$\lfloor \frac{n}{i}\rfloor$相同

void subtask2() {int ans = 0;for( int r = n, l;r > 0;r = l - 1 ) {if( r == 1 ) break;l = n / ( n / r + 1 ) + 1;int t = n / r;ans = ( ans + t % mod * ( r - l + 1 ) % mod ) % mod;}printf( "%lld\n", ans );
}

---

m=3,k=1

假设$n$足够大且存在$x_1<x_2<x_3$满足
$$\{\begin{array}{l}{x}_1\mid (x_1+x_2+x_3)\\ x_2\mid (x_1+x_2+x_3)\\ x_3\mid (x_1+x_2+x_3)\end{array}$$
不失一般性假设正整数$1<x<y<z$，即$1>\frac{1}{x}>\frac{1}{y}>\frac{1}{z}$

满足
$$\begin{gathered} \{\begin{array}{l}z\ast x_1=x_1+x_2+x_3\\ y\ast x_2=x_1+x_2+x_3\\ x\ast x_3=x_1+x_2+x_3\end{array} \\ \Rightarrow \{\begin{array}{l}\frac{x_1}{x_1+x_2+x_3}=\frac{1}{z}\\ \frac{x_2}{x_1+x_2+x_3}=\frac{1}{y}\\ \frac{x_3}{x_1+x_2+x_3}=\frac{1}{x}\end{array} \end{gathered}$$
则有$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$，且$1=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}<\frac{3}{x}\Rightarrow x<3\Rightarrow x=2$

因此$\frac{1}{y}+\frac{1}{z}=\frac{1}{2}=\frac{y+z}{yz}\Rightarrow 2(y+z)-yz=0\Rightarrow (y-2)(z-2)=4$

从而解出了唯一解$x=2,y=3,z=6$

于是，有
$$\begin{gathered} \{\begin{array}{l}6\ast x_1=x_1+x_2+x_3\\ 3\ast x_2=x_1+x_2+x_3\\ 2\ast x_3=x_1+x_2+x_3\end{array} \\ \Rightarrow 6x_1=3x_2=2x_3 \end{gathered}$$
令$k=x_1\Rightarrow x_2=2k,x_3=3k$

所以$(x_1,x_2,x_3)=(k,2k,3k),k\in N^{+}$，在$n\ge 3$时存在

要满足$x_1,x_2,x_3\le n$，所以$k$的取值范围为$[1,\lfloor \frac{n}{3}\rfloor ]$

答案为$$\lfloor \frac{n}{3}\rfloor$$

void subtask3() {printf( "%lld\n", ( n / 3 ) % mod );	
}

---

m=3,k=2

不妨假设正整数$x_1<x_2<x_3$

因为
$$\{\begin{array}{l}(x_1+x_3)\nmid x_2\Rightarrow (x_1+x_3)\nmid (x_1+x_2+x_3)\\ (x_2+x_3)\nmid x_1\Rightarrow (x_2+x_3)\nmid (x_1+x_2+x_3)\end{array}$$
所以只可能有$(x_1+x_2)\mid x_3\Rightarrow (x_1+x_2)\mid (x_1+x_2+x_3)$

尝试枚举$x_1+x_2=i$，得到$x_3$的取值个数（与m=2,k-1的求法一样)

再求出$i$拆分成$x_1+x_2$的拆分方案，利用乘法原理求得最后答案

枚举$x_1$后（实际上不可能在代码里枚举）便可唯一确定$x_2$的取值

对于和为$i$而言：如果$x_1=i-1$，则$x_2=1$；$\dots$ ；如果$x_1=1$，则$x_2=i-1$，一定有$i-1$种拆分方法

但是集合{2,3}\{2,3\}{2,3}和集合{3,2}\{3,2\}{3,2}是没有区别的，所以形如$a+b$的拆分被算了两次，且不合法的形如$a+a$的拆分也被算了一次

先减去不合法的$a+a$形式拆分（如果存在的话，显然这种拆分存在当且仅当$i$为偶数）

再除以二就是$a+b$形式的拆分个数了

同样的，我们需要分块来做

答案为$$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor \frac{i-1-[2|i]}{2}$$

void subtask6() {
/*
(i-1-[2|i])/2
通过打表发现
1->0
2->0
3->1
4->1
...
所以如果是奇数 就是/2
如果是偶数 那么就是/2-1
相当于是两组等差数列
注意l开局的奇偶即可
*/int ans = 0;for( int l = 1, r;l <= n;l = r + 1 ) {r = n / ( n / l );int c = 0;//x首相 y项数 因为有两组所以不用/2了if( l & 1 ) {int len = r - l + 1;int x = l / 2 % mod;int y = len / 2 % mod;c = ( c + ( x + x + y - 1 ) % mod * y % mod ) % mod;if( len & 1 ) c = ( c + r / 2 ) % mod;}else {int x = l / 2 - 1;c = ( c + x % mod ) % mod;int len = r - l;int y = len / 2 % mod;x ++;c = ( c + ( x + x + y - 1 ) % mod * y % mod ) % mod;if( len & 1 ) c = ( c + r / 2 ) % mod;}ans = ( ans + n / r % mod * c % mod ) % mod;}printf( "%lld\n", ( ans + mod ) % mod );
}

---

m=4,k=1

假设$n$足够大且存在$x_1<x_2<x_3<x_4\to 1>\frac{1}{x_1}>\frac{1}{x_2}>\frac{1}{x_3}>\frac{1}{x_4}$，满足
$$\{\begin{array}{l}{x}_1|(x_1+x_2+x_3+x_4)\\ x_2|(x_1+x_2+x_3+x_4)\\ x_3|(x_1+x_2+x_3+x_4)\\ x_4|(x_1+x_2+x_3+x_4)\end{array}$$
不失一般性地假设$x<y<z<w$，满足
$$\{\begin{array}{l}{x}_1+x_2+x_3+x_4=w\ast x_1\\ x_1+x_2+x_3+x_4=z\ast x_2\\ x_1+x_2+x_3+x_4=y\ast x_3\\ x_1+x_2+x_3+x_4=x\ast x_4\end{array}$$
则，有$\frac{1}{x_1}+\frac{1}{x_2}+\frac{1}{x_3}+\frac{1}{x_4}=1$

假设$x\ge 3$，则$\frac{1}{x_1}+\frac{1}{x_2}+\frac{1}{x_3}+\frac{1}{x_4}\le \frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}<1$

假设矛盾，所以$1<x<3\Rightarrow x=2$

假设$y\ge 6$，则$\frac{1}{x_2}+\frac{1}{x_3}+\frac{1}{x_4}\le \frac{1}{6}+\frac{1}{7}+\frac{1}{8}<\frac{1}{2}$

假设矛盾，所以$2<y<6\Rightarrow y=2/3/4$

• $y=3$，有$(z-6)(w-6)=36\to (2,3,7,42);(2,3,8,24);(2,3,9,18);(2,3,10,15)$
• $y=4$，有$(z-4)(w-4)=16\to (2,3,5,20);(2,4,6,12)$
• $y=5$，有$(3z-10)(3w-10)=100\to \varnothing$

所以整理一下，结果为

$(x_1,x_2,x_3,x_4)=(k,2k,3k,6k);;(k,2k,6k,9k);;(k,3k,8k,12k);;(k,4k,5k,10k);;(k,6k,14k,21k);;(2k,3k,10k,15k)$

（反解过程，上面有示范，这里不再展开计算）

所以在$n\ge 6$的时候才会全都成立，当$n=4/5$就手玩硬算

答案为
$$\{\begin{array}{l}1n=4,5\\ \lfloor \frac{n}{6}\rfloor +\lfloor \frac{n}{9}\rfloor +\lfloor \frac{n}{10}\rfloor +\lfloor \frac{n}{12}\rfloor +\lfloor \frac{n}{15}\rfloor +\lfloor \frac{n}{21}\rfloor n\ge 6\end{array}$$

void subtask4() {if( n == 4 or n == 5 ) printf( "1\n" );else printf( "%lld\n", ( n / 6 % mod + n / 9 % mod + n / 10 % mod + n / 12 % mod + n / 15 % mod + n / 21 % mod ) % mod );
}

---

m=4,k=2

不妨假设正整数$x_1<x_2<x_3<x_4$，则有
$$\{\begin{array}{l}(x_2+x_4)\nmid (x_1+x_3)\Rightarrow (x_2+x_4)\nmid (x_1+x_2+x_3+x_4)\\ (x_3+x_4)\nmid (x_1+x_2)\Rightarrow (x_3+x_4)\nmid (x_1+x_2+x_3+x_4)\end{array}$$
假设$n$足够大且存在$x_1<x_2<x_3<x_4$，满足
$$\{\begin{array}{l}(x_1+x_2)\mid (x_1+x_2+x_3+x_4)\Rightarrow (x_1+x_2)\mid (x_3+x_4)\\ (x_1+x_3)\mid (x_1+x_2+x_3+x_4)\Rightarrow (x_1+x_3)\mid (x_2+x_4)\\ (x_1+x_4)\mid (x_1+x_2+x_3+x_4)\Rightarrow x_1+x_4=x_2+x_3\\ (x_2+x_3)\mid (x_1+x_2+x_3+x_4)\Rightarrow x_1+x_4=x_2+x_3\end{array}$$
因为$x_2<x_3<x_4$，所以$x_2+x_4$不可能大于等于$x_4$的三倍，只能是$x_4$的两倍多（毕竟$x_4$要$+x_1$）

设$s(x_1+x_3)=x_2+x_4=2x_2+x_3-x_1<3(x_1+x_3)$

所以$1<s<3\Rightarrow s=2$

设$t(x_1+x_2)=x_3+x_4=5x_2-7x_1<5(x_1+x_2)$

所以$2=s<t<5\Rightarrow t=3/4$

推出$(x_1,x_2,x_3,x_4)=(k,5k,7k,11k);;(k,11k,19k,20k)$

在$n\ge 11$时，满足假设条件，$n<11$的情况直接手玩
$$\{\begin{array}{l}1n=4,5,6\\ 3n=7\\ 6n=8\\ 9n=9\\ 10n=10\\ \lfloor \frac{n}{11}\rfloor +\lfloor \frac{n}{29}n\ge 11\end{array}$$

void subtask5() {if( n == 4 or n == 5 or n == 6 ) printf( "1\n" );else if( n == 7 ) printf( "3\n" );else if( n == 8 ) printf( "6\n" );else if( n == 9 ) printf( "9\n" );else if( n == 10 ) printf( "10\n" );else printf( "%lld\n", ( n / 11 % mod + n / 29 % mod ) % mod );
}

---

m=4,k=3

不妨假设正整数$x_1<x_2<x_3<x_4$，有
$$\{\begin{array}{l}(x_1+x_2+x_4)\nmid x_3\Rightarrow (x_1+x_2+x_4)\nmid (x_1+x_2+x_3+x_4)\\ (x_1+x_3+x_4)\nmid x_2\Rightarrow (x_1+x_3+x_4)\nmid (x_1+x_2+x_3+x_4)\\ (x_3+x_2+x_4)\nmid x_1\Rightarrow (x_3+x_2+x_4)\nmid (x_1+x_2+x_3+x_4)\end{array}$$
所以只可能有

$(x_1+x_2+x_3)\mid x_4\Rightarrow (x_1+x_2+x_3)\mid (x_1+x_2+x_3+x_4)$

通过枚举$i=x_1+x_2+x_3$，确定$x_4$的个数$n-i$，再计算$i$拆分的方案，乘法原理即可求得最后答案

考虑计算拆分方案：假想枚举$x_1$，则$a+b+c$的形式会被计算$6$次，$a+a+b$的形式会被计算$3$次，$a+a+a$的形式会被计算$1$次

当$x_1=1,2,...i-2$，则$x_2=[1,i-2],...,[1,1]$

所以方案数为$(i-2)+(i-1)+...+1=\frac{(i-1)(i-2)}{2}$

我们如果能减去这些不合法的形式，再除以六就是拆分的最终方案数了

显然，$a+a+b$的形式能被计算到，当且仅当$a\in [1,\lfloor \frac{i-1}{2}\rfloor ]$。$a+a+a$的形式能被计算到，当且仅当$i=3a$

我们可以再假想枚举$x_2$，来减掉$a+a+b$的形式， 即$-3\lfloor \frac{i-1}{2}\rfloor$，将这个暴力拆开与上面的合并，则会发现$i$为偶数的时候，多减了$\frac{3}{2}$，要加回来

但这样$a+a+a$形式就会被减去三次，多减了两次，需要加回来$2[3|i]$（别忘了这个形式存在的前提是$i=3a$），这个的基础是最后总数$/6$，但是答案的表示是$/12$

所以上面分子写的是$4$的系数

所以答案是
$$\{\begin{array}{l}1n=4\\ 5n=5\\ {\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor \frac{i^2-6i+5+3[2|i]+4[3|i]}{12}n\ge 6\end{array}$$
但是又因为涉及分块，所以计算一段区间内$2,3$的倍数个数，简直要命，主要是左端点开头，救命！！

void subtask7() {if( n == 4 ) printf( "1\n" );else if( n == 5 ) printf( "5" );else {int ans = 0, lst = 0, inv2 = qkpow( 2, mod - 2 ), inv3 = qkpow( 3, mod - 2 ), inv12 = qkpow( 12, mod - 2 );for( int l = 1, r;l <= n;l = r + 1 ) {r = ( n / ( n / l ) );int len = r - l + 1;int now = r % mod * ( ( r + 1 ) % mod ) % mod * ( ( r % mod * 2 + 1 ) % mod ) % mod * inv2 % mod * inv3 % mod;int c = ( now - lst + mod ) % mod;c = ( c - ( l % mod + r % mod ) % mod * ( len % mod ) % mod * inv2 % mod * 6 % mod + mod ) % mod;c = ( c + len % mod * 5 % mod + mod ) % mod;lst = now;c = ( c + ( len / 2 % mod + ( len & 1 and ! ( l & 1 ) ) ) * 3 % mod ) % mod;c = ( c + ( len / 3 % mod + ( ( len % 3 != 0 ) and ( ( l % 3 == 0 ) or ( len % 3 == 2 and l % 3 == 2 ) ) ) ) * 4 % mod ) % mod;c = c * inv12 % mod;ans = ( ans + n / r % mod * c % mod ) % mod;}printf( "%lld\n", ans );}
}

code

#include <cstdio>
#include <cmath>
using namespace std;
#define mod 1000000007
#define int long long
int n, m, k;int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans;
}void subtask1() {int ans = 1;for( int i = n;i > n - m;i -- )ans = i % mod * ans % mod;for( int i = 1;i <= m;i ++ )ans = ans * qkpow( i, mod - 2 ) % mod;printf( "%lld\n", ans );
}void subtask2() {int ans = 0;for( int r = n, l;r > 0;r = l - 1 ) {if( r == 1 ) break;l = n / ( n / r + 1 ) + 1;int t = n / r;ans = ( ans + t % mod * ( r - l + 1 ) % mod ) % mod;}printf( "%lld\n", ans );
}void subtask3() {printf( "%lld\n", ( n / 3 ) % mod );	
}void subtask4() {if( n == 4 or n == 5 ) printf( "1\n" );else printf( "%lld\n", ( n / 6 % mod + n / 9 % mod + n / 10 % mod + n / 12 % mod + n / 15 % mod + n / 21 % mod ) % mod );
}void subtask5() {if( n == 4 or n == 5 or n == 6 ) printf( "1\n" );else if( n == 7 ) printf( "3\n" );else if( n == 8 ) printf( "6\n" );else if( n == 9 ) printf( "9\n" );else if( n == 10 ) printf( "10\n" );else printf( "%lld\n", ( n / 11 % mod + n / 29 % mod ) % mod );
}void subtask6() {int ans = 0;for( int l = 1, r;l <= n;l = r + 1 ) {r = n / ( n / l );int c = 0;if( l & 1 ) {int len = r - l + 1;int x = l / 2 % mod;int y = len / 2 % mod;c = ( c + ( x + x + y - 1 ) % mod * y % mod ) % mod;if( len & 1 ) c = ( c + r / 2 ) % mod;}else {int x = l / 2 - 1;c = ( c + x % mod ) % mod;int len = r - l;int y = len / 2 % mod;x ++;c = ( c + ( x + x + y - 1 ) % mod * y % mod ) % mod;if( len & 1 ) c = ( c + r / 2 ) % mod;}ans = ( ans + n / r % mod * c % mod ) % mod;}printf( "%lld\n", ( ans + mod ) % mod );
}void subtask7() {if( n == 4 ) printf( "1\n" );else if( n == 5 ) printf( "5" );else {int ans = 0, lst = 0, inv2 = qkpow( 2, mod - 2 ), inv3 = qkpow( 3, mod - 2 ), inv12 = qkpow( 12, mod - 2 );for( int l = 1, r;l <= n;l = r + 1 ) {r = ( n / ( n / l ) );int len = r - l + 1;int now = r % mod * ( ( r + 1 ) % mod ) % mod * ( ( r % mod * 2 + 1 ) % mod ) % mod * inv2 % mod * inv3 % mod;int c = ( now - lst + mod ) % mod;c = ( c - ( l % mod + r % mod ) % mod * ( len % mod ) % mod * inv2 % mod * 6 % mod + mod ) % mod;c = ( c + len % mod * 5 % mod + mod ) % mod;lst = now;c = ( c + ( len / 2 % mod + ( len & 1 and ! ( l & 1 ) ) ) * 3 % mod ) % mod;c = ( c + ( len / 3 % mod + ( ( len % 3 != 0 ) and ( ( l % 3 == 0 ) or ( len % 3 == 2 and l % 3 == 2 ) ) ) ) * 4 % mod ) % mod;c = c * inv12 % mod;ans = ( ans + n / r % mod * c % mod ) % mod;}printf( "%lld\n", ans );}
}signed main() {freopen( "vegetable.in", "r", stdin );freopen( "vegetable.out", "w", stdout );scanf( "%lld %lld %lld", &n, &m, &k );if( m == k ) subtask1();else if( m == 2 and k == 1 ) subtask2();else if( m == 3 and k == 1 ) subtask3();else if( m == 4 and k == 1 ) subtask4();else if( m == 4 and k == 2 ) subtask5();else if( m == 3 and k == 2 ) subtask6();else subtask7();return 0;
}