题解 Division Game
2024-10-19 18:30:01
Description
懒得写了。
Solution
设 \(f(x)\) 表示对于一个位置操作了 \(x\) 次后刚好变为 \(1\) 的方案数，可以看出的是 \(f(x)\) 同样也是对于一个位置在操作了 \(x-1\) 次后仍没有变为 \(1\) 的方案数。
可以想到的是，第 \(i\) 个位置结束的方案数就是：
\[\sum_{x=0} f(x+1)^{i-1}f(x)^{k-i+1}
\]
\]
考虑如何求 \(f(x)\) ，可以想到 \(f(x)\) 对应的是：有 \(m\) 种球，每种有 \(e_i\) 个，分到 \(x\) 个盒子中，不允许有盒子空着的方案数。设 \(g(x)=\prod_{i=1}^{m} \binom{e_i+x-1}{x-1}\)，那么我们就可以容斥得到 \(f(x)\)：
\[f(x)=\sum_{i=0}^{x} (-1)^{x-i}g(i)\binom{x}{i}
\]
\]
直接卷就好了。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 985661441
#define MAXN 1000005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int up = 400000,fac[MAXN],ifac[MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){
int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);
return res;
}
void Sub (int &a,int b){a = dec (a,b);}
void Add (int &a,int b){a = add (a,b);}
int binom (int a,int b){return a >= b ? mul (fac[a],mul (ifac[b],ifac[a - b])) : 0;}
#define SZ(A) ((A).size())
typedef vector<int> poly;
int w[MAXN],rev[MAXN];
void init_ntt(){
int lim = 1 << 18;
for (Int i = 0;i < lim;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << 17);
int Wn = qkpow (3,(mod - 1) / lim);w[lim >> 1] = 1;
for (Int i = lim / 2 + 1;i < lim;++ i) w[i] = mul (w[i - 1],Wn);
for (Int i = lim / 2 - 1;~i;-- i) w[i] = w[i << 1];
}
void ntt (poly &a,int type){
#define G 3
#define Gi 328553814
static int d[MAXN];int lim = a.size();
for (Int i = 0,z = 18 - __builtin_ctz(lim);i < lim;++ i) d[rev[i] >> z] = a[i];
for (Int i = 1;i < lim;i <<= 1)
for (Int j = 0;j < lim;j += i << 1)
for (Int k = 0;k < i;++ k){
int x = mul (w[i + k],d[i + j + k]);
d[i + j + k] = dec (d[j + k],x),d[j + k] = add (d[j + k],x);
}
for (Int i = 0;i < lim;++ i) a[i] = d[i] % mod;
if (type == -1){
reverse (a.begin() + 1,a.begin() + lim);
for (Int i = 0,Inv = qkpow (lim,mod - 2);i < lim;++ i) a[i] = mul (a[i],Inv);
}
#undef G
#undef Gi
}
poly operator * (poly A,poly B){
int lim = 1,l = 0,len = SZ(A) + SZ(B) - 1;
while (lim < SZ(A) + SZ(B)) lim <<= 1,++ l;
A.resize (lim),B.resize (lim),ntt (A,1),ntt (B,1);
for (Int i = 0;i < lim;++ i) A[i] = mul (A[i],B[i]);
ntt (A,-1),A.resize (len);
return A;
}
poly operator * (poly a,int b){
for (Int i = 0;i < SZ(a);++ i) a[i] = mul (a[i],b);
return a;
}
poly operator + (poly a,poly b){
int len = max (SZ(a),SZ(b));
a.resize (len),b.resize (len);
for (Int i = 0;i < len;++ i) Add (a[i],b[i]);
return a;
}
poly operator - (poly a,poly b){
int len = max (SZ(a),SZ(b));
a.resize (len),b.resize (len);
for (Int i = 0;i < len;++ i) Sub (a[i],b[i]);
return a;
}
poly operator + (poly a,int b){
Add (a[0],b);
return a;
}
poly operator - (poly a,int b){
Sub (a[0],b);
return a;
}
poly f;
poly inv (poly &A,int n){
if (n == 1) return poly (1,qkpow (A[0],mod - 2));
poly Now,G0 = inv (A,(n + 1) >> 1);Now.resize (n);
for (Int i = 0;i < n;++ i)
if (i < SZ(A)) Now[i] = A[i];
else Now[i] = 0;
poly res = G0 * 2 - G0 * Now * G0;res.resize (n);
return res;
}
poly inv (poly A){return inv (A,SZ(A));}
poly der (poly A){
for (Int i = 1;i < SZ(A);++ i) A[i - 1] = mul (A[i],i);
A.pop_back ();
return A;
}
int getinv (int x){return mul (ifac[x],fac[x - 1]);}
poly inter (poly A){
A.push_back (0);
for (Int i = SZ(A) - 2;~i;-- i) A[i + 1] = mul (A[i],getinv (i + 1));
A[0] = 0;
return A;
}
poly ln (poly a,int n){
poly res = inter (inv (a,n) * der (a));
res.resize (n);
return res;
}
poly ln (poly a){return ln (a,SZ(a));}
void putout (poly a){
cout << SZ(a) << ": ";for (Int i = 0;i < SZ(a);++ i) cout << a[i] << " ";cout << endl;
}
poly exp (poly &a,int n){
if (n == 1) return poly (1,1);
poly Now,G0 = exp (a,(n + 1) >> 1);Now.resize (n);
for (Int i = 0;i < n;++ i) Now[i] = a[i];
poly res = G0 - G0 * (ln(G0,n) - Now);res.resize (n);
return res;
}
poly exp (poly a){return exp (a,SZ(a));}
int n,m,k,e[MAXN],p[MAXN];
void Work (){
n = 1;
for (Int i = 1;i <= m;++ i) read (p[i],e[i]),n += e[i];
poly F,G;F.resize (n + 1),G.resize (n + 1);
for (Int i = 1;i <= n;++ i){
int tmp = 1;
for (Int k = 1;k <= m;++ k) tmp = mul (tmp,binom (e[k] + i - 1,i - 1));
G[i] = mul (ifac[i],tmp);
}
for (Int i = 0;i <= n;++ i) F[i] = mul (ifac[i],i & 1 ? mod - 1 : 1);
// for (Int i = 0;i < SZ(F);++ i) cout << mul (fac[i],F[i]) << " ";cout << endl;
// for (Int i = 0;i < SZ(G);++ i) cout << mul (fac[i],G[i]) << " ";cout << endl;
F = F * G;
for (Int i = 0;i < SZ(F);++ i) F[i] = mul (F[i],fac[i]);
// for (Int i = 0;i < SZ(F);++ i) cout << F[i] << " ";cout << endl;
// cout << n << endl;
for (Int i = 1;i <= k;++ i){
int res = 0;
for (Int h = 0;h < n;++ h)
// cout << i << " , " << h << ": " << mul (qkpow (F[h + 1],i - 1),qkpow (F[h],k - i + 1)) << endl,
Add (res,mul (qkpow (F[h + 1],i - 1),qkpow (F[h],k - i + 1)));
write (res),putchar (' ');
}
putchar ('\n');
}
signed main(){
init_ntt ();
fac[0] = 1;for (Int i = 1;i <= up;++ i) fac[i] = mul (fac[i - 1],i);
ifac[up] = qkpow (fac[up],mod - 2);for (Int i = up;i;-- i) ifac[i - 1] = mul (ifac[i],i);
int tot = 0;while (~scanf ("%d%d",&m,&k)) printf ("Case #%d: ",++ tot),Work ();
return 0;
}
最新文章
- 漫谈Linux内核哈希表(1)
- 软件代码生成之Codesmith模板.netTiers
- 文件上传（js, C#）
- 如何试用Office 365 及 SharePoint Online(美版)
- IntelliJ IDEA设置自动导入包
- linux Apache和php配置
- 编写jquery插件的分享
- Codeforces Round #241 (Div. 2)->A. Guess a number!
- 用户控件（.ascx）与<ul><li>以及<a>布局之小结
- Java -- WeakHashMap
- Eval与Bind的区别
- 树莓派配置允许WINDOWS远程桌面 x11nvc+xrdp
- 通知：QQ互联网回调地址校验加强
- Java模仿http请求工具类
- 一个系统部署多个tomcat实例
- face recognition[MobiFace]
- SpringBoot 配置文件存放位置及读取顺序
- oracle 创建create user 及授权grant 查看登陆的用户
- EF更新指定字段.或个更新整个实体
- V-rep学习笔记：力传感器