【WC2014】时空穿梭

Problem

WC2014
uoj54

Analysis

请先思考后再展开

完整数据范围请前往uoj
如果对像本sb一样对高维空间难以理解,可以看看bzoj3518帮助理解

因为在一条直线上,考虑枚举线段两端的节点
那么我们不妨枚举跨度向量a,那么在中间的点的数量就是 $gcd(a_i)-1$ ,这个挺好想的吧,因为右上角的节点会被所有【除以gcd的位置】覆盖
考虑每种向量实际有多少个,那么不难得出柿子(如果选不到c-2个,组合数为0)
$$
\begin{aligned}
ans&=\sum_{a_t}^{M_t} \sum \sum C_{gcd(a_t)-1}^{c-2} (\prod M_t-a_t)\\
&=\sum_{g=1}^{minM} C_{g-1}^{c-2} \times ( \sum_{m_t=1}^{M_t/g} \sum \sum (\prod M_t-m_t \times g) \times [gcd(m)=1] )\\
&然后套路地莫反一下(目的是取消之间的依赖性,利用乘法分配律降低复杂度)\\
&=\sum_{g=1}^{minM} C_{g-1}^{c-2} \times ( \sum_{m_t=1}^{M_t/g} \sum \sum (\prod M_t-m_t \times g) \times (\sum_{d|gcd(m_i)} \mu(d)) )\\
&=\sum_{g=1}^{minM} C_{g-1}^{c-2} \times ( \sum_{d=1}^{minM/g} \mu(d) \times \prod (\sum_{i=1}^{\frac{M_t}{dg}} M_t-i \times dg) )\\
&看到这个形式,做题多的不难发现枚举dg会方便很多\\
&=\sum_{D=1}^{minM} (\prod ( \sum_{i=0}^{\frac{M_t}{D}} M_t-i \times D )) \times (\sum_{g|D} C_{g-1}^{c-2} \mu(D/g))\\
&=\sum_{D=1}^{minM} (\prod ( (M_t/D) \times M_t-D \times (M_t/D)*(M_t/D+1)/2 )) \times (\sum_{g|D} C_{g-1}^{c-2} \mu(D/g))\\
\end{aligned}
$$
后面那个 cmlogm 预处理为f(c,D),则每组数据的复杂度为nmlogm
到此为止都比较常规,然而还是无法处理多组数据,主要在于致命的枚举D
此时很多人肯定会观察到式子中的整除,公所周知现在不同的 $\frac{M_t}{D}$ 只有 $n \sqrt m$ 个
但是看到柿子中还有一个D,非常麻烦,但也仅仅只有这个东西是麻烦的,于是我们不妨把D当做未知数!
所以我们依然可以用数论分块得出当前D的区间dl和dr,
这段区间内中间的东西是个关于D的多项式,可以 $n^2$ 计算出 $D^i$ 的系数a
$ans=\sum_{i=0}^n a_i \times ( \sum_{dl}^{dr} f(D) \times D^i )$
后面那个可以cnM计算前缀和

组合数用递推式算
f(i,c,D)枚举倍数暴力预处理
总复杂度为 $O(cmlogm+cnm+Tn^3\sqrt m)$

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
95
96
97
98
99
100
101
102
103
104
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
const int MOD=10007;
void add(int &x,int y)
{
x+=y;if(x>=MOD) x-=MOD;
if(x<=-MOD) x+=MOD;
}
int sum(int x,int y) {add(x,y);return x;}
const int MAX_N=12,MAX_M=100001;
bool no[MAX_M];int pr=0,prime[MAX_M],mu[MAX_M];
void pre()
{
mu[1]=1;
for(int i=2;i<MAX_M;i++)
{
if(!no[i]) prime[++pr]=i,mu[i]=-1;
for(int j=1;j<=pr and (ll)i*prime[j]<MAX_M;j++)
{
int t=i*prime[j];no[t]=1;
if(i%prime[j]==0) {mu[t]=0;break;}
mu[t]=-mu[i];
}
}
}
int aa[MAX_N];
int C[MAX_M][30],f[30][MAX_M],ff[MAX_N][30][MAX_M];
int m[MAX_N];
void main()
{
pre();
C[0][0]=1;
for(int i=1;i<MAX_M;i++)
{
C[i][0]=1;
for(int j=1;j<30 and j<=i;j++) C[i][j]=sum(C[i-1][j-1],C[i-1][j]);
}
for(int D=1;D<MAX_M;D++)
for(int c=2;c<=20;c++)
for(int j=D;j<MAX_M;j+=D) add(f[c][j], C[D-1][c-2]*mu[j/D] );
for(int i=0;i<MAX_N;i++)
for(int D=1;D<MAX_M;D++)
{
int Di=1;for(int j=1;j<=i;j++) Di=Di*D%MOD;
for(int c=2;c<=20;c++)
ff[i][c][D]=f[c][D]*Di%MOD,add(ff[i][c][D],ff[i][c][D-1]);
}
int T;scanf("%d",&T);
while(T--)
{
int n,c;scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++) scanf("%d",&m[i]);
sort(m+1,m+n+1);
int ans=0;
for(int D=1;D<=m[1]-1;)
{
int lst=m[1];for(int i=1;i<=n;i++) lst=min(lst,m[i]/(m[i]/D));
memset(aa,0,sizeof aa);aa[0]=1;
for(int i=1;i<=n;i++)
{
int t=(m[i]/D)%MOD;int a=t*m[i]%MOD,b=(-t*(t+1)/2)%MOD;
for(int j=n;j>=1;j--) aa[j]=sum(aa[j]*a%MOD,aa[j-1]*b%MOD);
aa[0]=aa[0]*a%MOD;
}
for(int i=0;i<=n;i++) add(ans, aa[i]*(ff[i][c][lst]-ff[i][c][D-1])%MOD );
D=lst+1;
}
printf("%d\n",(ans+MOD)%MOD);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6b1.html
转载请注明出处,谢谢!