广州个人网站搭建,网站用户体验存在问题,WordPress显示时间函数,营销型网站是什么题意#xff1a;TTT 组数据#xff0c;给一个 nnn 维空间#xff0c;第 iii 维大小为 [1,mi]∩Z[1,m_i]\cap \Z[1,mi]∩Z#xff0c;求大小为 ccc 的严格偏序上升的共线点集个数。答案模 100071000710007。 T≤100,n≤11,m≤105,c≤20T\leq 100,n\leq 11,m\leq 10^5,c\le…题意TTT 组数据给一个 nnn 维空间第 iii 维大小为 [1,mi]∩Z[1,m_i]\cap \Z[1,mi]∩Z求大小为 ccc 的严格偏序上升的共线点集个数。答案模 100071000710007。
T≤100,n≤11,m≤105,c≤20T\leq 100,n\leq 11,m\leq 10^5,c\leq 20T≤100,n≤11,m≤105,c≤20
神仙题
设空间大小向量为 mmm,MMM 为坐标最大值。下文中若未特殊说明对向量无公开定义的运算均定义为其每一维坐标的运算。
考虑第一个点到最后一个点的差向量 xxx它中间有 gcd(x)−1\gcd(x)-1gcd(x)−1 个空隙可以放gcd\gcdgcd 为所有坐标数值的 gcd\gcdgcd。所以
ans∑x≤m(gcd(x)−1c−2)∏i1n(mi−xi)ans\sum_{x\leq m}\binom{\gcd(x)-1}{c-2}\prod_{i1}^n(m_i-x_i)ansx≤m∑(c−2gcd(x)−1)i1∏n(mi−xi)
看到有个 gcd\gcdgcd 想到反演。
ans∑d1M(d−1c−2)∑x≤m[gcd(x)d]∏i1n(mi−xi)∑d1M(d−1c−2)∑x≤md[gcd(x)1]∏i1n(mi−dxi)∑d1M(d−1c−2)∑x≤md∑k∣xμ(k)∏i1n(mi−dxi)∑d1M(d−1c−2)∑k∣xμ(k)∑x≤mdk∏i1n(mi−dkxi)∑d1M∑x≤md∏i1n(mi−dxi)∑k∣d(k−1c−2)μ(dk)ans\sum_{d1}^M\binom{d-1}{c-2}\sum_{x\leq m}[\gcd(x)d]\prod_{i1}^n(m_i-x_i)\\ \sum_{d1}^M\binom{d-1}{c-2}\sum_{x\leq \frac{m}{d}}[\gcd(x)1]\prod_{i1}^n(m_i-dx_i)\\ \sum_{d1}^M\binom{d-1}{c-2}\sum_{x\leq \frac{m}{d}}\sum_{k\mid x}\mu (k)\prod_{i1}^n(m_i-dx_i)\\ \sum_{d1}^M\binom{d-1}{c-2}\sum_{k\mid x}\mu (k)\sum_{x\leq \frac{m}{dk}}\prod_{i1}^n(m_i-dkx_i)\\ \sum_{d1}^M\sum_{x\leq \frac md}\prod_{i1}^n(m_i-dx_i)\sum_{k\mid d}\binom{k-1}{c-2}\mu (\frac dk)ansd1∑M(c−2d−1)x≤m∑[gcd(x)d]i1∏n(mi−xi)d1∑M(c−2d−1)x≤dm∑[gcd(x)1]i1∏n(mi−dxi)d1∑M(c−2d−1)x≤dm∑k∣x∑μ(k)i1∏n(mi−dxi)d1∑M(c−2d−1)k∣x∑μ(k)x≤dkm∑i1∏n(mi−dkxi)d1∑Mx≤dm∑i1∏n(mi−dxi)k∣d∑(c−2k−1)μ(kd)
令 g(n)∑d∣n(d−1c−2)μ(nd)g(n)\sum\limits_{d\mid n}\binom{d-1}{c-2}\mu(\frac nd)g(n)d∣n∑(c−2d−1)μ(dn),这个随便预处理一下就能算出来。
ans∑d1M∑x≤md∏i1n(mi−dxi)g(d)∑d1Mg(d)∏i1n∑x1⌊mid⌋(mi−dx)ans\sum_{d1}^M\sum_{x\leq \frac md}\prod_{i1}^n(m_i-dx_i)g(d)\\ \sum_{d1}^Mg(d)\prod_{i1}^n\sum_{x1}^{\left\lfloor\frac{m_i}{d}\right\rfloor}(m_i-dx)ansd1∑Mx≤dm∑i1∏n(mi−dxi)g(d)d1∑Mg(d)i1∏nx1∑⌊dmi⌋(mi−dx)
这样大概是 O(Tmnlogn)\Omicron(Tmn\log n)O(Tmnlogn) 的有点卡。
看到整除立刻想到整除分块。
注意到后面是一个关于 ddd 的 nnn 次多项式每个和式次数为 111如果要整除分块的话只需要求这个多项式的前缀和。
设这个多项式系数为 aia_iai,那么一次区间查询
∑dlrg(d)f(d)∑dlrg(d)∑i0naidi∑i0nai∑dlrg(d)di\sum_{dl}^rg(d)f(d)\\ \sum_{dl}^rg(d)\sum_{i0}^na_id^i\\ \sum_{i0}^na_i\sum_{dl}^rg(d)d^idl∑rg(d)f(d)dl∑rg(d)i0∑naidii0∑naidl∑rg(d)di
后面是和询问无关的直接预处理就可以 O(n)\Omicron(n)O(n) 回答。
现在的问题是如何维护多项式。 整除分块时一共变化了 O(nm)\Omicron(n\sqrt m)O(nm) 次每次变化的时候把操作的 111 次多项式做一个多项式乘法或除法就可以了。
然后是喜闻乐见的除 000 问题。记下除了几个 000 多项式即可但其他人都没提到这个代码也看不懂一脸懵逼可能写法不太一样吧……
复杂度大概是 O(ncmTn2m)\Omicron(ncmTn^2\sqrt m)O(ncmTn2m)
#include iostream
#include cstdio
#include cstring
#include cctype
using namespace std;
typedef long long ll;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
const int MOD10007;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
inline int qpow(int a,int p)
{int ans1;a%MOD;while (p){if (p1) ansans*a%MOD;aa*a%MOD,p1;}return ans;
}
const int N1e5,MAXNN5;
int np[MAXN],pl[MAXN],cnt;
inline void init()
{np[1]1;for (int i2;iN;i){if (!np[i]) pl[cnt]i;for (int j1,x;(xi*pl[j])N;j){np[x]1;if (i%pl[j]0) break;}}
}
int C[MAXN][20],g[22][MAXN],S[12][22][MAXN];
int a[12],n,c,lim[12],m[12],zero;
inline void mul(int x,int y)
{if (!x!y) return (void)(zero);for (int in;i1;i--) a[i](a[i-1]*xa[i]*y)%MOD;a[0]a[0]*y%MOD;
}
inline void div(int x,int y)
{if (!y){if (!x) return (void)(--zero);int ixqpow(x,MOD-2);for (int i0;in;i) a[i]a[i1]*ix%MOD;a[n]0; return;}int iyqpow(y,MOD-2);a[0]a[0]*iy%MOD;for (int i1;in;i) a[i]dec(a[i],a[i-1]*x%MOD)*iy%MOD;
}
inline int calc(int d,int l,int r)
{for (int i1;in;i){int curm[i]/d;if (curlim[i]){div(dec(0,lim[i]*(lim[i]1ll)/2%MOD),(ll)lim[i]*m[i]%MOD);lim[i]cur;mul(dec(0,lim[i]*(lim[i]1ll)/2%MOD),(ll)lim[i]*m[i]%MOD);}}if (zero) return 0;int ans0;for (int i0;in;i) ans(ansa[i]*dec(S[i][c][r],S[i][c][l-1]))%MOD;return ans;
}
int main()
{init();C[0][0]1;for (int i1;iN;i){C[i][0]1;for (int j1;j20;j) C[i][j](C[i-1][j]C[i-1][j-1])%MOD;}for (int t2;t22;t){for (int i1;iN;i) g[t][i]C[i-1][t-2];for (int j1;jcnt;j)for (int iN/pl[j];i1;i--)g[t][i*pl[j]]dec(g[t][i*pl[j]],g[t][i]);for (int i0;i12;i)for (int d1;dN;d)S[i][t][d]add(S[i][t][d-1],qpow(d,i)*g[t][d]%MOD); }for (int Tread();T;T--){zero0;nread(),cread();int MN;for (int i1;in;i) Mmin(M,lim[i]m[i]read());memset(a,0,sizeof(a));a[0]1;for (int i1;in;i) mul(dec(0,m[i]*(m[i]1ll)/2%MOD),(ll)m[i]*m[i]%MOD);int ans0;for (int l1,r;lM;lr1){rM;for (int i1;in;i) rmin(r,m[i]/(m[i]/l));ansadd(ans,calc(l,l,r));}printf(%d\n,ans);}return 0;
}
