題意：$T$ 組數(shù)據(jù)，給一個(gè) $n$ 維空間，第 $i$ 維大小為 $[1,m_i]\cap \mathbb{Z}$，求大小為 $c$ 的嚴(yán)格偏序上升的共線點(diǎn)集個(gè)數(shù)。答案模 $10007$。

$T\le 100,n\le 11,m\le 10^5,c\le 20$

神仙題

設(shè)空間大小向量為 $m$,$M$ 為坐標(biāo)最大值。下文中若未特殊說明，對(duì)向量無(wú)公開定義的運(yùn)算均定義為其每一維坐標(biāo)的運(yùn)算。

考慮第一個(gè)點(diǎn)到最后一個(gè)點(diǎn)的差向量 $x$，它中間有 $\gcd (x)?1$ 個(gè)空隙可以放，$\gcd$ 為所有坐標(biāo)數(shù)值的 $\gcd$。所以

$$ans=\sum _{x\le m}\left(\genfrac{}{}{0ex}{}{\gcd (x)?1}{c?2}\right)\prod _{i=1}^n(m_i?x_i)$$

看到有個(gè) $\gcd$ ，想到反演。

$$\begin{gathered} ans=\sum _{d=1}^M\left(\genfrac{}{}{0ex}{}{d?1}{c?2}\right)\sum _{x\le m}[\gcd (x)=d]\prod _{i=1}^n(m_i?x_i) \\ =\sum _{d=1}^M\left(\genfrac{}{}{0ex}{}{d?1}{c?2}\right)\sum _{x\le \frac{m}{d}}[\gcd (x)=1]\prod _{i=1}^n(m_i?d{x}_i) \\ =\sum _{d=1}^M\left(\genfrac{}{}{0ex}{}{d?1}{c?2}\right)\sum _{x\le \frac{m}{d}}\sum _{k\mid x}\mu (k)\prod _{i=1}^n(m_i?d{x}_i) \\ =\sum _{d=1}^M\left(\genfrac{}{}{0ex}{}{d?1}{c?2}\right)\sum _{k\mid x}\mu (k)\sum _{x\le \frac{m}{dk}}\prod _{i=1}^n(m_i?dk{x}_i) \\ =\sum _{d=1}^M\sum _{x\le \frac{m}{d}}\prod _{i=1}^n(m_i?d{x}_i)\sum _{k\mid d}\left(\genfrac{}{}{0ex}{}{k?1}{c?2}\right)\mu (\frac{d}{k}) \end{gathered}$$

令 $g(n)=\sum _{d\mid n}\left(\genfrac{}{}{0ex}{}{d?1}{c?2}\right)\mu (\frac{n}{d})$,這個(gè)隨便預(yù)處理一下就能算出來(lái)。

$$\begin{gathered} ans=\sum _{d=1}^M\sum _{x\le \frac{m}{d}}\prod _{i=1}^n(m_i?d{x}_i)g(d) \\ =\sum _{d=1}^{M}g(d)\prod _{i=1}^n\sum _{x=1}^{?\frac{m_i}{d}?}(m_i?dx) \end{gathered}$$

這樣大概是 $\mathrm{O}(Tmn\log n)$ 的，有點(diǎn)卡。

看到整除，立刻想到整除分塊。

注意到后面是一個(gè)關(guān)于 $d$ 的 $n$ 次多項(xiàng)式（每個(gè)和式次數(shù)為 $1$），如果要整除分塊的話只需要求這個(gè)多項(xiàng)式的前綴和。

設(shè)這個(gè)多項(xiàng)式系數(shù)為 $a_i$,那么一次區(qū)間查詢

$$\begin{gathered} \sum _{d=l}^{r}g(d)f(d) \\ =\sum _{d=l}^{r}g(d)\sum _{i=0}^n{a}_i{d}^i \\ =\sum _{i=0}^n{a}_i\sum _{d=l}^{r}g(d)d^i \end{gathered}$$

后面是和詢問無(wú)關(guān)的，直接預(yù)處理就可以 $\mathrm{O}(n)$ 回答。

現(xiàn)在的問題是如何維護(hù)多項(xiàng)式。 整除分塊時(shí)一共變化了 $\mathrm{O}(n\sqrt{m})$ 次，每次變化的時(shí)候把操作的 $1$ 次多項(xiàng)式做一個(gè)多項(xiàng)式乘法或除法就可以了。

然后是喜聞樂見的除 $0$ 問題。記下除了幾個(gè) $0$ 多項(xiàng)式即可，但其他人都沒提到這個(gè)，代碼也看不懂，一臉懵逼，可能寫法不太一樣吧……

復(fù)雜度大概是 $\mathrm{O}(ncm+T{n}^2\sqrt{m})$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> using namespace std; typedef long long ll; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } const int MOD=10007; inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;} inline int dec(const int& x,const int& y){return x<y? x-y+MOD:x-y;} inline int qpow(int a,int p) {int ans=1;a%=MOD;while (p){if (p&1) ans=ans*a%MOD;a=a*a%MOD,p>>=1;}return ans; } const int N=1e5,MAXN=N+5; int np[MAXN],pl[MAXN],cnt; inline void init() {np[1]=1;for (int i=2;i<=N;i++){if (!np[i]) pl[++cnt]=i;for (int j=1,x;(x=i*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 i=n;i>=1;i--) a[i]=(a[i-1]*x+a[i]*y)%MOD;a[0]=a[0]*y%MOD; } inline void div(int x,int y) {if (!y){if (!x) return (void)(--zero);int ix=qpow(x,MOD-2);for (int i=0;i<n;i++) a[i]=a[i+1]*ix%MOD;a[n]=0; return;}int iy=qpow(y,MOD-2);a[0]=a[0]*iy%MOD;for (int i=1;i<=n;i++) a[i]=dec(a[i],a[i-1]*x%MOD)*iy%MOD; } inline int calc(int d,int l,int r) {for (int i=1;i<=n;i++){int cur=m[i]/d;if (cur<lim[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 ans=0;for (int i=0;i<=n;i++) ans=(ans+a[i]*dec(S[i][c][r],S[i][c][l-1]))%MOD;return ans; } int main() {init();C[0][0]=1;for (int i=1;i<=N;i++){C[i][0]=1;for (int j=1;j<20;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;}for (int t=2;t<22;t++){for (int i=1;i<=N;i++) g[t][i]=C[i-1][t-2];for (int j=1;j<=cnt;j++)for (int i=N/pl[j];i>=1;i--)g[t][i*pl[j]]=dec(g[t][i*pl[j]],g[t][i]);for (int i=0;i<12;i++)for (int d=1;d<=N;d++)S[i][t][d]=add(S[i][t][d-1],qpow(d,i)*g[t][d]%MOD); }for (int T=read();T;T--){zero=0;n=read(),c=read();int M=N;for (int i=1;i<=n;i++) M=min(M,lim[i]=m[i]=read());memset(a,0,sizeof(a));a[0]=1;for (int i=1;i<=n;i++) mul(dec(0,m[i]*(m[i]+1ll)/2%MOD),(ll)m[i]*m[i]%MOD);int ans=0;for (int l=1,r;l<=M;l=r+1){r=M;for (int i=1;i<=n;i++) r=min(r,m[i]/(m[i]/l));ans=add(ans,calc(l,l,r));}printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【WC2014】时空穿梭【组合数】【莫比乌斯反演】【整除分块】【暴力多项式】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。