ZOJ 3904 Birthday Gift【NTT】

2024-08-24 11:32
文章标签 zoj birthday gift ntt 3904

本文主要是介绍ZOJ 3904 Birthday Gift【NTT】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

首先,我们知道的是, num1+num2=N ,其中 num1 是Alice的盒子数, num2 是Bob的盒子数。
那么 ans[N]=Alice(num1)×Bob(Nnum1) ,明显是FFT的卷积形式。

接下来分析 Alice(num1) 的部分,下面直接称 num1=N
Alice(N) 有两种情况。
如果 N 是素数,那么就是将n1个糖果随机分在 N 个无区别的盒子里。此为第二类斯特林数。在固定了n1时,第二类斯特林数的NTT求法见此。
如果 N 是合数,那么就是从n1中挑 N1 个放入一个盒子,剩下的每个盒子中装一个。方案数为 CN1n1 ,记住用逆元。

分析 Bob(num2) 的部分,下面直接称 num2=N
Bob比较简单,首先先将 N 个箱子刷成M,且使得每个箱子颜色不同。方案就是 CNM
剩下的 n2 个糖果要划分到 N 个不同的位置,就是使用的隔板法。方案就是CN1n21

最后用NTT再求一个答案就行了。
注意上限的取值,比如Bob的盒子数 N 不能超过颜色数M

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define getidx(l,r) (l+r|l!=r)
#define ls getidx(l,mid)
#define rs getidx(mid+1,r)
#define lson l,mid
#define rson mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int maxn=50005;
const int MOD=786433;ll n1, n2, m, q;
bool p[maxn];
ll A[maxn], B[maxn], C[maxn], f[maxn], g[maxn], ans[maxn], fac[maxn], inv[maxn];ll qpow(ll a,ll b,ll p)
{ll base=a,res=1;while(b){if(b&1) res=res*base%p;base=base*base%p;b>>=1;}return res;
}namespace NTT
{
const int r=11,gl=20;
ll p,rp[50],irp[50];
void setMOD(ll _p=786433)
{p=_p;for(int i=0; i<gl; i++) rp[i]=qpow(r,(p-1)/(1<<i),p);
}
void FFT(ll a[],int n,ll wt[]=rp)
{for(int i=0,j=0; i<n; i++){if(j>i) swap(a[i],a[j]);int k=n;while(j&(k>>=1)) j&=~k;j|=k;}for(int m=1,b=1; m<n; m<<=1,b++)for(int k=0,w=1; k<m; k++){for(int i=k; i<n; i+=m<<1){int v=a[i+m]*w%p;if((a[i+m]=a[i]-v)<0) a[i+m]+=p;if((a[i]+=v)>=p) a[i]-=p;}w=w*wt[b]%p;}
}
void IFFT(ll a[], int n)
{for(int i=0; i<gl; i++) irp[i]=qpow(rp[i],n-1,p);FFT(a,n,irp);ll inv=qpow(n,p-2,p);for(int i=0; i<n; i++) a[i]=a[i]*inv%p;
}
void Mul(ll a[],ll b[],ll n,ll c[])
{int len = 1;while (len < n) len <<= 1;len <<= 1;FFT(a,len);FFT(b,len);for(int i=0; i<len; i++) c[i]=a[i]*b[i]%p;IFFT(c,len);
}
}int main()
{int T;memset(p, 1, sizeof(p));p[0] = p[1] = false;for (int i = 2; i <= maxn; i++)if (p[i]){int j = 2;while (i * j <= maxn){p[i*j] = false;j++;}}fac[0] = inv[0] = 1;for (int i = 1; i <= maxn; i++){fac[i] = fac[i-1]*i%MOD;inv[i] = inv[i-1]*qpow(i, MOD-2, MOD)%MOD;}read(T);while(T--){scanf("%lld%lld%lld%lld", &n1, &n2, &m, &q);memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));A[0]=1;for(int i=1; i<=n1; i++)  A[i]=A[i-1]*i%MOD;for(int i=0; i<=n1; i++)  A[i]=B[i]=qpow(A[i],MOD-2,MOD);for(int i=1; i<=n1; i+=2) A[i]=A[i]*(MOD-1)%MOD;for(int i=0; i<=n1; i++)  B[i]=B[i]*qpow(i,n1,MOD)%MOD;NTT::setMOD();NTT::Mul(A,B,n1+1,C);memset(f, 0, sizeof(f));memset(g, 0, sizeof(g));for (int i = 1; i <= n1 && i <= m; i++){if (p[i]) f[i] = C[i];else if (i == n1) f[i] = 1;else f[i] = fac[n1]*inv[i-1]%MOD*inv[n1-i+1]%MOD;}for (int i = 1; i <= n2 && i <= m; i++)g[i] = (fac[m]*inv[i]%MOD*inv[m-i]%MOD)*(fac[n2-1]*inv[i-1]%MOD*inv[n2-i]%MOD)%MOD;NTT::Mul(f,g,m+1,ans);for (int i = 1; i <= q; i++){int x;scanf("%d", &x);printf("%lld\n", ans[x]);}}return 0;
}

这篇关于ZOJ 3904 Birthday Gift【NTT】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102357

相关文章

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

zoj 4624

题目分析:有两排灯,每排n个,每个灯亮的概率为p,每个灯之间互不影响,亮了的灯不再灭,问两排中,每排有大于等于m个灯亮的概率。 设dp[ i ][ j ]为第一排亮了i个灯,第二排亮了j个灯,距离目标状态的期望天数。显然 i >= m ,j >= m时 , dp[ i ][ j ] = 0 。 状态转移 : 第一排亮了a个灯,a 在[ 0 , n - i] 之间,第二排亮了b个灯 , b 在

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g

CF629D Babaei and Birthday Cake

题意:给出N个半径,和高的圆柱,要求后面的体积比前面大的可以堆在前一个的上面,求最大的体积和。 dp[i]=max(dp[j])+v[i](j<i&&v[i]>v[j]); 离散化,线段树维护区间最大值 import java.io.BufferedInputStream;import java.io.BufferedOutputStream;import

ZOJ 3324 Machine(线段树区间合并)

这道题网上很多代码是错误的,由于后台数据水,他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度(就是最接近初始位置的高度),和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数,min_v 记录该区间最小高度 cover

【ZOJ】3362 Beer Problem 最小费用流

传送门:【ZOJ】3362 Beer Problem 题目分析:这道题本来应该很快就AC的,但是!因为我以前犯的一个致命错误导致我这题一天了到现在才调出来!唉。。失策。。貌似给的模板也有这个错误。。。马上就去改。。但是这个错误竟然还能过掉那么多的题。。害我还要一题一题的改回去。。 本题就是赤裸裸的最小费用流。 新建汇点t(源点即1),将所有的n-1个城市和汇点建边,容量为无穷大,

【ZOJ】2332 Gems 最大流——判断满流

传送门:【ZOJ】2332 Gems 题目分析:首先我们设立源点s,汇点t,s向所有宝石建边,容量为题目中给出的,然后所有可行的转换,向两个宝石之间建无向边,容量为INF,接下来所有的宝石向自己相应的类型建边,容量INF,所有的宝石向自己相应的颜色建边,容量INF。最后,所有的类型以及颜色向汇点建边,容量为题目中给出的。最后跑一遍最大流,如果满流,说明所有的宝石都成功的限制条件下分给了男主

【ZOJ】2532 Internship 最小割——关键割边

传送门:【ZOJ】2532 Internship 题目分析:题目意思很明显,问你能否增加一条边的容量使得流量增加,就是让求关键割边。关键割边怎么求?首先按照题意建图跑一遍最小割。之后在残余网络上进行dfs,将从源点s出发能到的点标记为1,将从汇点t出发能到的点重标记为2。一条边为关键割边当且仅当它为正向边且弧头标记为1,弧尾标记为2。 PS:注意dfs的细节,s出发沿正向残余网络,t出发