Portal --> 出錯啦qwq（好吧其實是沒有）

Description

　　給定兩個正整數\(n,k\)，選擇一些互不相同的正整數，滿足這些數的最小公倍數恰好為\(n\)，并且這些數的和為\(k\)的倍數

　　求選擇的方案數對\(232792561\)取模

　　數據范圍：多組數據，組數\(T<=10,n<=10^{18},k<=20\)，且\(n\)的所有質因子不大于\(100\)

Solution

　　這題。。好神仙啊qwq敲爆腦子都想不出來系列qwq

　　注意到\(n<=10^{18}\)意味著\(n\)至多有\(15\)個不同的質因子（前\(15\)個質數乘一下就知道了），并且\(k\)的范圍也是比較小的

　　然后還有一點就是這個模數比較有趣，它\(=lcm(1,2,...,20)+1\)，也就是說它可以對長度在\(1..20\)的區間DFT

?　　那不管別的我們可以先考慮一個最樸素的dp

　　記\(f[i][j]\)表示當前所選的數狀態為\(i\)，和\(\%k=j\)的方案數，其中這個“所選數的狀態”具體計算方式是：假設寫成分解質因數的形式后\(n=\sum p_i^{mi_i}\)，其中\(p_i\)為\(n\)的每一個不同的質因子，我們的狀態是一個二進制數，并且二進制的每一位對應一個\(n\)的質因子，對于二進制的第\(i\)位（假設對應\(p_i\)），如果說當前所選的數中存在一個數\(x\)滿足\(p_i^{mi_i}|x\)，那么這位為\(1\)，否則為\(0\)

?　　這樣一來，我們最后的答案就應該是\(f[(1<<Cnt)-1][0]\)，其中\(Cnt\)為\(n\)的不同質因子個數

　　至于求解。。分解質因數和預處理因數可以暴力求解，但是后面的dp直接暴力轉移的話穩穩的T啊（光枚舉子集就要\(3^{Cnt}\)了還要再乘個\(k\))，所以現在的問題是我們要怎么比較快速地轉移

?　　觀察這個dp兩維的轉移，我們會發現第一維的轉移可以寫成一個集合或卷積的形式（或起來等于某個數就把值累計進去），而第二維的轉移則直接枚舉因數什么的大力轉移就好了

　　然后這里有一個很有意思的想法：首先我們發現這兩維如果可以分開處理就會比較好一點，然后注意到這個模數很有趣，允許我們進行區間長度\(\in[1,20]\)的DFT，而DFT操作之后，dp的這兩維在某種意義上就是獨立的了，換句話來說，如果說我們先在同行內轉移\(f\)數組，再對轉以后每行的不完全計算的\(f\)數組做一次DFT，這行的\(f\)的第二維就不會互相影響了，也就是說我們可以通過這種方式實現第一維和第二維轉移的分離

　　這樣我們就可以先處理\(f[][i]\)，直觀一點來說就是先在同行轉移\(f\)數組，具體一點就是枚舉\(n\)的因數，然后考慮加進去的貢獻，也就是假設當前枚舉到的因數是\(a[i]\)，\(a[i]\)對應的狀態是\(st\)，那么我們可以對于所有的\(j\in [0,k)\)轉移：
\[ f[st][(j+a[i]\%k)]+=f'[st][j] \]
?　　之所以在后面的\(f\)打了個\('\)是因為我們這里要累加進去的是用\(a[i]\)更新前的\(f[st]\)的版本

?　　

?　　這樣我們就得到了整合了同行數據之后的\(f\)數組（為了防止弄混在接下來的描述中我們還是將這個不完全轉移的\(f\)數組記為\(f1\)好了），然后對于每一行DFT一下，接下來就是考慮第一維的轉移了，更加直觀一點就是。。同列的\(f\)進行轉移

?　　接下來為了讓描述變得更加簡潔，我們將第二維省去（因為反正轉移的時候都是同列轉移）

?　　現在我們要做的事情就是挑出若干個\(f1[i]\)，滿足\(i_1\ or\ i_2\ or\ ...\ i_m=st\)然后將這堆\(f1[i]\)的值累加到\(f[st]\)去

　　我們記\(F(S)=\sum\limits_{i\subseteq S}f[i]\)，如果說我們知道了\(F(S)\)的取值，那么只要大力容斥一下就可以得出\(f\)數組了，具體一點的話就是：
\[ f[T]=\sum\limits_{S\subseteq T}(-1)^{|T|-|S|}F(S) \]
　　我們將\(F(S)\)進行一下轉化，會發現：
\[ \begin{aligned} F(S)&=\sum\limits_{j\subseteq S}f[j]\\ &=\prod\limits_{i\subseteq S}(1+f1[i]) \end{aligned} \]
　　具體的話就是因為對于\(f\)來說，每一個\(f[j]\)都是由若干個\(f1[i]\)組成的，我們考慮將第二個等號后面的連乘的括號拆掉，展開之后會發現囊括了\(i\)的所有組合方式（為了方便理解可以自己用比較小的規模模擬一下），然后因為我們限制了\(i\subseteq S\)所以可以保證任意的組合方式都是滿足組合后\(\subseteq S\)的

?　　然后由于\(f1\)是已知的，所以我們現在就要想如何快速求\(F(S)\)

　　顯然枚舉子集不現實

?　　如果我們直接從小到大枚舉狀態，每次將這個狀態對應的\(f1\)值轉移的話，可能會出現重復計算的情況（比如說\(010\)可以轉移到\(011\)和\(110\)，而\(011\)和\(110\)又都可以轉移到\(111\)，這樣如果按照這種轉移方式的話，\(111\)這里\(010\)的\(f1\)值就會被重復計算），所以這里考慮一種很玄學的按順序轉移方式：

?　　我們考慮二進制一位一位轉移，從低位枚舉到高位，每枚舉一位就把所有的這位為\(0\)的狀態的值累加到將這位修改為\(1\)后的狀態里面去，具體一點的話就是：

?　　我們以\(Cnt=3\)為例子，狀態轉移大概是這樣：

　　其中橙黃色的箭頭表示轉移的方向，然后位數是從最右邊開始數的

?　　這樣的話顯然所有的狀態都能轉移到它能轉移到的位置，現在我們來說明一下為什么這樣不會重復計算：首先可以確認的一點是，這種重復計算的情況只會出現在轉移到一個被修改了兩個及以上位的狀態的時候，而我們這樣的枚舉方式每次只轉移到修改了一位的地方，并且是按照數位從低到高，狀態從小到大的順序轉移，比如說剛才提到的\(010\)在\(111\)中被重復計算的情況，放在這個轉移方式中就應該是：在轉移第一位的時候，\(010\)會先轉移到\(011\)，然后在轉移第三位的時候再由累加了\(010\)的\(011\)轉移到\(111\)，每次都是從只修改一位的地方轉移過來，不會出現重復計算的情況（但其實上面的證明也不算。。特別嚴謹。。還是感性理解既視感qwq）

?　　然后我們就可以在\(O(2^{Cnt})\)的時間內求得\(F(S)\)，接下來直接大力容斥一下就可以得出\(f[(1<<Cnt)-1][0]\)的值最后IDFT一下就可以得出答案啦

　　

　　代碼大概長這個樣子

#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int MOD=232792561,G=71,N=110; const int p[26]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}; ll mi[N],rec_mx[N],Tmp[N],have[N]; ll a[500010]; int f[(1<<15)+10][20]; ll n,K,T,Cnt,all; void add(int &x,int y){x=(1LL*x+y+MOD)%MOD;} bool in(int st,int x){return st>>(x-1)&1;} int St(int x){return 1<<x-1;} int ksm(int x,int y){int ret=1,base=x;for (;y;y>>=1,base=1LL*base*base%MOD)if (y&1) ret=1LL*ret*base%MOD;return ret; } namespace DFT{/*{{{*/int tmp[110],W[1010][2];int inv;void init(){int rt=ksm(G,(MOD-1)/K);W[0][0]=1;for (int i=1;i<=1000;++i)W[i][0]=1LL*W[i-1][0]*rt%MOD;for (int i=0;i<=1000;++i)W[i][1]=ksm(W[i][0],MOD-2);}void dft(int *a,int n,int op){for (int i=0;i<n;++i) tmp[i]=0;for (int i=0;i<n;++i) for (int j=0;j<n;++j)tmp[i]=(1LL*tmp[i]+1LL*a[j]*W[i*j][op==-1]%MOD)%MOD;if (op==-1){inv=ksm(n,MOD-2);for (int i=0;i<n;++i) tmp[i]=1LL*tmp[i]*inv%MOD;}for (int i=0;i<n;++i) a[i]=tmp[i];} }/*}}}*/ void Div(ll x){for (int i=1;i<=25;++i)if (x%p[i]==0){++Cnt; rec_mx[Cnt]=1; mi[Cnt]=0; have[Cnt]=p[i];while (x%p[i]==0) x/=p[i],++mi[Cnt],rec_mx[Cnt]*=p[i];} } void dfs(int now,ll prod){if (now>Cnt){a[++a[0]]=prod;return;}ll tmp=prod;for (int i=0;i<=mi[now];++i){dfs(now+1,tmp);tmp*=have[now];} } void prework(){a[0]=0; Cnt=0;Div(n);dfs(1,1); } void update(int st,int r){for (int i=0;i<K;++i) Tmp[i]=f[st][i];for (int i=0;i<K;++i) add(f[st][(i+r)%K],Tmp[i]); } void solve(){int st,op;memset(f,0,sizeof(f));all=(1<<Cnt)-1;for (int i=0;i<=all;++i) f[i][0]=1;//initfor (int i=1;i<=a[0];++i){st=0;for (int j=1;j<=Cnt;++j)if (a[i]%rec_mx[j]==0) st|=St(j);update(st,a[i]%K);}for (int i=0;i<=all;++i)DFT::dft(f[i],K,1);for (int i=1;i<=Cnt;++i)for (int j=0;j<=all;++j)if (in(j,i))for (int k=0;k<K;++k)f[j][k]=1LL*f[j][k]*f[j^St(i)][k]%MOD;for (int i=0;i<all;++i){op=1;for (int j=1;j<=Cnt;++j)if (!in(i,j)) op*=-1;for (int j=0;j<K;++j)add(f[all][j],op*f[i][j]);}DFT::dft(f[all],K,-1);printf("%d\n",f[all][0]); }int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin); #endifscanf("%d",&T);for (int o=1;o<=T;++o){scanf("%lld%lld",&n,&K);DFT::init();prework();solve();} }

轉載于:https://www.cnblogs.com/yoyoball/p/9362927.html

總結

以上是生活随笔為你收集整理的【2018北京集训（六）】Lcm的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。