牛客 无限手套
输入描述:
第一行一个正整数m表示宝石的种类(1<=m<=1000)接下来M行,每行两个正整数ai, bi(0<=ai, bi<=10^9)接下来一行正整数q,共有q次询问(1<=q<=1000)接下来q行每行一个正整数n询问如果无限手套可以安装n个宝石则力量之和是多少。(1<=n<=10000)
输出描述:
一共q行,每行一个正整数表示答案。答案对998244353取模。
示例1
输入
2 2 1 1 0 2 3 4
输出
74 193
题解
考虑对每一个宝石的生成函数为
化简过程:
其中也许令你迷惑的是
推导过程如下:
m种宝石的生成函数相乘
对于我们用幂级数展开,展开方法为:
于是式子转化为两个多项式相乘
最后的系数即为所求
代码
// #include <bits/stdc++.h> #include <iostream> #include <algorithm> #include <cstdio> #include <queue> #include <cmath> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <vector> #include <assert.h> #include <cmath> #include <ctime> using namespace std; #define me(x,y) memset((x),(y),sizeof (x)) #define MIN(x,y) ((x) < (y) ? (x) : (y)) #define MAX(x,y) ((x) > (y) ? (x) : (y)) #define SGN(x) ((x)>0?1:((x)<0?-1:0)) #define ABS(x) ((x)>0?(x):-(x)) // #define int __int128_t typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int maxn = 1e5+10; const int inf = __INT32_MAX__; const ll INF = __LONG_LONG_MAX__; const ll MOD = 998244353; const double eps = 1e-8; const double pi = std::acos(-1); const string cars[] = {"🚗","🚕","🚙"}; ll f[maxn],finv[maxn],inv[maxn]; void init(){ inv[1] = 1; for(int i = 2; i < maxn;++i) inv[i] = 1ll*(MOD-MOD/i)*inv[MOD%i]%MOD; f[0] = finv[0] = 1; for(int i = 1; i < maxn; ++i){ f[i] = f[i-1]*i%MOD; finv[i] = finv[i-1]*inv[i]%MOD; } } ll comb(int n,int m){ if(m < 0 || m > n) return 0; return f[n]*finv[n-m]%MOD*finv[m]%MOD; } ll x[maxn]; int main(){ ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("1in.in","r",stdin); freopen("1out.out","w",stdout); #endif init(); int a,b,A,B,C,m;cin>>m; x[0] = 1; for(int i = 1; i <= m; ++i){ cin>>a>>b; A = a-b+1,B = a+b-2,C = 1; A = (A%MOD+MOD)%MOD,B = (B%MOD+MOD)%MOD; for(int j = 2*i; j >= 2; --j) x[j] = (x[j]*C%MOD+x[j-1]*B%MOD+x[j-2]*A%MOD)%MOD; x[1] = (x[1]*C%MOD+x[0]*B%MOD)%MOD; x[0] = x[0]*C%MOD; } int q;cin>>q; while(q--){ int n;cin>>n; ll sum = 0; for(int i = 0; i <= n; ++i) sum = (sum+comb(3*m+i-1,i)*x[n-i]%MOD)%MOD; cout<<sum<<endl; } return 0; }