description

小皮球在計(jì)算出答案之后，買了一堆皮膚，他心里很開(kāi)心，但是一不小心，就忘記自己買了哪些皮膚了。= =|||
萬(wàn)幸的是，他還記得他把所有皮膚按照 1～N 來(lái)編號(hào)，他買來(lái)的那些皮膚的編號(hào)（他至少買了一款皮膚），最大公約數(shù)是 G，最小公倍數(shù)是 L。
現(xiàn)在，有 Q 組詢問(wèn)，每組詢問(wèn)輸入一個(gè)數(shù)字 X，請(qǐng)你告訴小皮球，有多少種合法的購(gòu)買方案中，購(gòu)買了皮膚 X？
因?yàn)榇鸢柑罅?#xff0c;所以你只需要輸出答案 mod1000000007 即可。

輸入格式
第一行，三個(gè)數(shù)字 N,G,L，如題意所示。
第二行，一個(gè)數(shù)字 Q，表示詢問(wèn)個(gè)數(shù)。
第三行，Q 個(gè)數(shù)字，表示每個(gè)詢問(wèn)所問(wèn)的 X

輸出格式
對(duì)于每一組詢問(wèn)，在一行中單獨(dú)輸出一個(gè)整數(shù)，表示這個(gè)詢問(wèn)的答案。

樣例
Input
5 1 30
5
1 2 3 4 5
Output
1
2
2
0
2

數(shù)據(jù)范圍與提示
30%的數(shù)據(jù)：N≤20
50% 的數(shù)據(jù)：N≤1000
70% 的數(shù)據(jù)：N≤100000
100% 的數(shù)據(jù)：$N,G,L\le 10^8,Q\le 10^5,1\le X\le 10^8$

solution

先不考慮強(qiáng)制選$x$的情況

先把$n/G,L/G$，轉(zhuǎn)化為求$gcd=1,lcm=L/G$的方案數(shù)
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$L\le 1e8$，分解質(zhì)因子即不超過(guò)$8$個(gè)
這么小考慮狀壓

如何保證$gcd=1$
證明某個(gè)被選擇的皮膚有一個(gè)$L$的質(zhì)因子對(duì)應(yīng)的指數(shù)為$0$，即不含該質(zhì)因子
如何保證$lcm=L$
證明某個(gè)被選擇的皮膚有一個(gè)$L$的質(zhì)因子對(duì)應(yīng)的指數(shù)與$L$相同
$L$的每一個(gè)質(zhì)因子都有某個(gè)皮膚指數(shù)與之分解后相同
且所有的都不能超過(guò)

那么狀壓分為兩類
前一半表示質(zhì)因子的指數(shù)是否為$0$，后一半表示質(zhì)因子的指數(shù)是否達(dá)到$L$上界

顯然有些皮膚分解后對(duì)應(yīng)的狀態(tài)是一樣的，統(tǒng)計(jì)在一起即可
狀態(tài)數(shù)似乎$650$內(nèi)

現(xiàn)在加上$x$強(qiáng)制入選的要求，就單列出來(lái)
設(shè)$f$表示前綴積，$g$表示后綴積
$$ans[i]=val[i\to S^{\prime }]?\sum _{S}f[i?1][S]\times g[i+1][S]$$
發(fā)現(xiàn)可以將$f,g$用$FW{T}_{or}$卷起來(lái)

具體可看代碼

code

代碼經(jīng)過(guò)各種取模優(yōu)化，快讀優(yōu)化，吸氧才堪堪跑過(guò)

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define mod 1000000007 vector < int > num; int n, G, L, Q, N, cnt, tot; int p[10], e[10]; int id[650], s[1 << 16], sum[650], ans[650]; int h[650][1 << 16], f[650][1 << 16], g[650][1 << 16];void read( int &x ) {x = 0; int f = 1; char s = getchar();while( s < '0' || s > '9' ) {if( s == '-' ) f = -1;s = getchar();}while( '0' <= s && s <= '9' ) {x = ( x << 1 ) + ( x << 3 ) + ( s - '0' );s = getchar();}x *= f; }int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = 1ll * ans * x % mod;x = 1ll * x * x % mod;y >>= 1;}return ans; }void init( int x ) {for( int i = 2;i * i <= x;i ++ ) {if( x % i == 0 ) {p[++ tot] = i;while( x % i == 0 ) x /= i, e[tot] ++;}}if( x > 1 ) p[++ tot] = x, e[tot] = 1; }int calc( int x ) {int S = 0;for( int i = 1;i <= tot;i ++ ) {int t = 0;while( x % p[i] == 0 ) x /= p[i], t ++;if( t == 0 ) S |= ( 1 << ( i - 1 ) );if( t == e[i] ) S |= ( 1 << ( i - 1 + tot ) );}return S; }int add( int x, int y ) {x += y;if( x > mod ) return x - mod;return x; }int sub( int x, int y ) {x -= y;if( x < 0 ) return x + mod;return x; }void FWT_or( int *v, int f ) {for( int i = 1;i < N;i <<= 1 )for( int j = 0;j < N;j += ( i << 1 ) )for( int k = 0;k < i;k ++ )if( f == 1 ) v[j + k + i] = add( v[j + k + i], v[j + k] );else v[j + k + i] = sub( v[j + k + i], v[j + k] ); }int main() {read( n ), read( G ), read( L ), read( Q );if( L % G ) {while( Q -- ) {int x;read( x );printf( "0\n" );}return 0;}L /= G, n /= G, init( L );for( int i = 1;i <= n && i * i <= L;i ++ ) {if( L % i ) continue;num.push_back( i );if( L / i <= n && i * i != L )num.push_back( L / i );}for( int i = 0;i < num.size();i ++ )s[calc( num[i] )] ++;N = 1 << ( tot << 1 ); for( int i = 0;i < N;i ++ )if( s[i] ) id[++ cnt] = i, sum[cnt] = qkpow( 2, s[i] ) - 1;f[0][0] = g[cnt + 1][0] = 1;for( int i = 1;i <= cnt;i ++ )for( int S = 0;S < N;S ++ ) {f[i][S] = add( f[i][S], f[i - 1][S] );f[i][S | id[i]] = add( f[i][S | id[i]], 1ll * f[i - 1][S] * sum[i] % mod );}for( int i = cnt;i;i -- )for( int S = 0;S < N;S ++ ) {g[i][S] = add( g[i][S], g[i + 1][S] );g[i][S | id[i]] = add( g[i][S | id[i]], 1ll * g[i + 1][S] * sum[i] % mod );}for( int i = 0;i <= cnt;i ++ ) FWT_or( f[i], 1 );for( int i = 1;i <= cnt + 1;i ++ ) FWT_or( g[i], 1 );for( int i = 1;i <= cnt;i ++ ) for( int S = 0;S < N;S ++ )h[i][S] = 1ll * f[i - 1][S] * g[i + 1][S] % mod;for( int i = 1;i <= cnt;i ++ ) FWT_or( h[i], -1 );for( int i = 1;i <= cnt;i ++ ) {for( int S = 0;S < N;S ++ )if( ( S | id[i] ) == N - 1 )ans[i] = add( ans[i], h[i][S] );ans[i] = 1ll * ans[i] * qkpow( 2, s[id[i]] - 1 ) % mod;}while( Q -- ) {int x;read( x );if( x % G ) {printf( "0\n" );continue;}x /= G;if( L % x || x > n ) {printf( "0\n" );continue;}int p = lower_bound( id + 1, id + cnt + 1, calc( x ) ) - id;printf( "%d\n", ans[p] );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[SNOI2017]遗失的答案 （FWT）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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