听说是冬令营少见的可做的题目?好像比较下我参加过的冬令营, 确实是一个良心的题目啊。

作为一个看上去就像是化式子题的题目, 这个题还是有一点新意的。

就是没有把难点放在怎么“筛”的问题上。

题目链接

题目大意

一个\(n\)维平面选取一条直线上的\(c\)个整点, 第\(i\)维坐标\(\leqslant m_i\), 的方案数。

解题报告

因为两点确定一条直线, 加上整点的限定, 所以可以先枚举选取的点构成的线段的每一维坐标的长度\(l_i\).

在确定每一维坐标的长度的前提下, 可以得到每一维坐标的最小值的范围\(m_i-l_i\).

在多维空间中的一条线段上的整点个数为\(\text{gcd}(l_1,l_2,l_3,...,l_n) - 1\).

不妨设\(m_1 \leqslant \text{min} \lbrace m_2,m_3,...,m_n \rbrace\)

然后就可以列出式子: \[ \begin{aligned} \text{ans} & = \sum_{l_1=1}^{m_1} \sum_{l_2=1}^{m_2} ... \sum_{l_n=1}^{m_n} \prod_{i=1}^{n} (m_i - l_i) {\text{gcd}(l_1,l_2,...,l_n)-1 \choose c-2}\\ &= \sum_{d=1}^{m_1} {d-1 \choose c-2} \sum_{l_1 d \leqslant m_1} ... \sum_{l_nd \leqslant m_n} \prod_{i=1}^{n}(m_i-l_id) [\text{gcd}(l_1,l_2,...,l_n) = 1] \\ &= \sum_{d=1}^{m_1} {d-1 \choose c-2} \sum_{dk \leqslant m_1} \mu(k) \sum_{l_1 kd \leqslant m_1} ... \sum_{l_nkd \leqslant m_n} \prod_{i=1}^{n}(m_i-l_ikd) \\ &= \sum_{k=1}^{m_1} \sum_{l_1k \leqslant m_1} ... \sum_{l_n k \leqslant m_n} \prod_{i=1}^{n}(m_i-l_ik) \sum_{d|k} \mu(\frac{k}{d}){d-1 \choose c-2} \end{aligned} \] 这个式子可以重写下: \[ \text{ans} = \sum_{k=1}^{m_1} g(k) f(k) \] 其中, \(f(k) = \sum_{d|k} \mu(\frac{k}{d}){d-1 \choose c-2}\) 这个可以使用\(n \ln n\)的筛法直接预处理得到。

但是\(g(k) = \sum_{l_1k \leqslant m_1} ... \sum_{l_n k \leqslant m_n} \prod_{i=1}^{n}(m_i-l_ik)\) 如果暴力算, 复杂度爆炸。

继续化简 \[ \begin{aligned} g(k) & = \prod_{i=1}^{n} \sum_{l_i \leqslant \lfloor \frac{m_i}{k} \rfloor} (m_i-l_ik) \\ & = \prod_{i=1}^{n} (m_i * \lfloor \frac{m_i}{k} \rfloor - k*\frac{\lfloor \frac{m_i}{k} \rfloor * (\lfloor \frac{m_i}{k} \rfloor+1) }{2}) \\ & = \sum_{i=0}^{n} g_i * k^i \end{aligned} \] 然后, \[ \begin{aligned} \text{ans} & = \sum_{k=1}^{m_1} \sum_{i=0}^{n} g_i * k^i f(k) \\ &= \sum_{i=0}^{n} g_i \sum_{k=1}^{m_1} k^if(k) \end{aligned} \]

这样复杂度是\(O(Tn^3\sqrt{m}+ cm \ln m)\)

有的时候题目难在std过于暴力让人不敢相信。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
typedef long long ll;
const int N=12;
const int C=21;
const int M=100010;
const int T=1010;
const int p=10007;
int f[N][C][M], g[C][M];
int pm[M], pn, mu[M];
bool no[M];
int _n[T],cc[T],mm[T][N],test;
int n,c,m,mi[N],as;
int k[N],bio[M][C];
inline void in(int &x) {
char c=getchar(); int f=1;
for (;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:f);
for (x=0; c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
x*=f;
}
inline void cmx(int &x,int a) { x=(a>x?a:x); }
inline void cmn(int &x,int a) { x=(a<x?a:x); }
inline int mo(int x,int y) { x+=y; if (x>=p) x-=p; if(x<0) x+=p; return x; }
inline void inital() {
no[1]=1, mu[1]=1;
rep(i,2,m) {
if (!no[i]) pm[++pn]=i, mu[i]=-1;
for (int j=1; j<=pn&&pm[j]*i<=m; ++j) {
no[pm[j]*i]=1;
if (i%pm[j]==0) break;
else mu[pm[j]*i]=-mu[i];
}
}
bio[0][0]=1;
rep(i,1,m) { bio[i][0]=1; rep(j,1,19)
bio[i][j]=mo(bio[i-1][j],bio[i-1][j-1]);
}
rep(c,2,20) rep(i,1,m) if (mu[i])
for (int j=i,k=1; j<=m; j+=i,++k)
g[c][j]=mo(g[c][j],bio[k-1][c-2]*mu[i]);
rep(i,1,m) rep(c,2,20) {
int t=1; rep(n,0,11) {
f[n][c][i]=mo(f[n][c][i-1],t*g[c][i]%p);
t=t*i%p;
}
}
}
inline void muls(int x) {
memset(k,0,sizeof(k)); k[0]=1;
int a, b, B;
rep(i,1,n) {
B=mi[i]/x;
a=(ll)B*mi[i]%p, b=mo(p,-(ll)B*(B+1)/2%p);
vep(j,n,1) k[j]=mo(k[j]*a%p,k[j-1]*b%p);
k[0]=k[0]*a%p;
}
}
int main() {
in(test); m=0;
rep(i,1,test) {
in(_n[i]),in(cc[i]);
rep(j,1,_n[i]) in(mm[i][j]),cmx(m,mm[i][j]);
}
inital();
rep(ts, 1, test) {
n=_n[ts], c=cc[ts];
m=M, as=0;
rep(i,1,n) mi[i]=mm[ts][i], cmn(m, mi[i]);
for (int i=1, j; i<=m; i=j+1) {
j=M; rep(kk,1,n) cmn(j,mi[kk]/(mi[kk]/i));
muls(i);
rep(kk,0,n) as=mo(as,k[kk]*(f[kk][c][j]-f[kk][c][i-1])%p);
}
printf("%d\n", as);
}
return 0;
}

留言