Submission #38482013

---

Source Code Expand

#include<bits/stdc++.h>
#define vecI vector<int>
using namespace std;
const int N=1e6+5,mod=998244353;
int kuai(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
	return ans;
}
vecI operator+(vecI a,vecI b){
	if(a.size()<b.size())swap(a,b);
	for(int i=0;i<b.size();i++)a[i]=(a[i]+b[i])%mod;
	return a;
}
struct Poly{
	int cnt[N],S,Gi,G=3;
	void NTT(int *A,int T){
		for(int i=0;i<S;i++)if(i<cnt[i])swap(A[i],A[cnt[i]]);
		for(int len=1;len<S;len<<=1){
			int W=kuai(T?G:Gi,(mod-1)/(len*2));
			for(int L=0;L<S;L+=len*2){
				int now=1;
				for(int k=0;k<len;k++,now=1ll*now*W%mod){
					int x=A[L+k],y=1ll*now*A[L+k+len]%mod;
					A[L+k]=(x+y)%mod,A[L+k+len]=(x-y+mod)%mod;
				}
			}
		}
	}
	int A[N],B[N],l;
	vecI mul(vecI &a,vecI &b){
		int n=a.size()-1,m=b.size()-1;
		Gi=kuai(G,mod-2);for(S=1,l=0;S<=n+m;S<<=1,l++);
		for(int i=0;i<=S;i++)A[i]=B[i]=0;
		for(int i=0;i<=n;i++)A[i]=a[i];for(int i=0;i<=m;i++)B[i]=b[i];
		for(int i=0;i<=S;i++)cnt[i]=(cnt[i>>1]>>1)+((i&1)<<(l-1));
		NTT(A,1),NTT(B,1);
		for(int i=0;i<=S;i++)A[i]=1ll*A[i]*B[i]%mod;
		NTT(A,0);
		int Inv=kuai(S,mod-2);
		vecI res(n+m+1);
		for(int i=0;i<=n+m;i++)res[i]=1ll*A[i]*Inv%mod;
		return res;
	}
}Poly;
vecI operator*(vecI a,vecI b){return Poly.mul(a,b);}
struct Frac{vecI a,b;};
Frac operator*(Frac a,Frac b){return {a.a*b.b+a.b*b.a,a.b*b.b};}
vecI Inv(vecI &A, int s){
	vecI X={kuai(A[0],mod-2)};
    while(X.size() < s){
        vecI temp(A.begin(), A.begin() + min(A.size(), 2 * X.size())),nx = X * X * temp;
        X.resize(2 * X.size());
        for(int i = 0; i < X.size(); i++)X[i] = (2ll * X[i]%mod - nx[i]+mod)%mod;
    }
    X.resize(s);
    return X;
}
template<class T> 
T solve(vector<T> V){
	if(V.size()==1) return V[0];
	int mid = V.size() / 2;
	vector<T> lft(V.begin(), V.begin() + mid);
	vector<T> rgt(V.begin() + mid, V.end());
	T A = solve(lft), B = solve(rgt);
	return A*B;
}
int jie[N],ni[N];
void pre(int n){
	jie[0]=1;
	for(int i=1;i<=n;i++)jie[i]=1ll*jie[i-1]*i%mod;
	ni[n]=kuai(jie[n],mod-2);
	for(int i=n;i;i--)ni[i-1]=1ll*ni[i]*i%mod;
}
int n,m;
int main(){
	cin>>n>>m;
	pre(max(n,m));
	int s=1;
	for(int i=1;i<n;i++)s=1ll*s*(n-i)%mod*kuai(n,mod-2)%mod;
	vecI a(m+1);
	for(int i=0;i<=m;i++)a[i]=1ll*kuai(n,i)%mod*s%mod*ni[i]%mod;
	vector<vecI> vec(n);
	for(int i=0;i<n;i++)vec[i]={1,mod-1ll*i*kuai(n,mod-2)%mod};
	vecI b=solve(vec);
	vector<Frac> tmp(b.size());
	for(int i=0;i<b.size();i++)tmp[i]={{b[i]},{1,mod-i}};
	Frac c=solve(tmp);
	b=Inv(c.b,m+1);
	b=c.a*Inv(c.b,m+1);
	for(int i=0;i<=m;i++)b[i]=1ll*b[i]*ni[i]%mod;
	b=Inv(b,m+1);
	a=a*b;
	for(int i=1;i<=m;i++)cout<<1ll*a[i]*jie[i]%mod<<'\n';
}

Submission Info

Compile Error

./Main.cpp: In function ‘std::vector<int> operator+(std::vector<int>, std::vector<int>)’:
./Main.cpp:12:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   12 |  for(int i=0;i<b.size();i++)a[i]=(a[i]+b[i])%mod;
      |              ~^~~~~~~~~
./Main.cpp: In member function ‘std::vector<int> Poly::mul(std::vector<int>&, std::vector<int>&)’:
./Main.cpp:35:3: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   35 |   for(int i=0;i<=n;i++)A[i]=a[i];for(int i=0;i<=m;i++)B[i]=b[i];
      |   ^~~
./Main.cpp:35:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   35 |   for(int i=0;i<=n;i++)A[i]=a[i];for(int i=0;i<=m;i++)B[i]=b[i];
      |                                  ^~~
./Main.cpp: In function ‘std::vector<int> Inv(std::vector<int>&, int)’:
./Main.cpp:51:20: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   51 |     while(X.size() < s){
      |           ~~~~~~~~~^~~
./Main.cpp:54:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   54 |         for(int i = 0; i < X.size(); i++)X[i] = (2ll * X[i]%mod - nx[i]+mod)%mod;
      |                        ~~^~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:84:35: warning: narrowing conversion of ‘(((long long int)((int)mod)) - (((1 * ((long long int)i)) * ((long long int)kuai(n, (((int)mod) - 2)))) % ((long long int)((int)mod))))’ from ‘long long int’ to ‘int’ [-Wnarrowing]
   84 |  for(int i=0;i<n;i++)vec[i]={1,mod-1ll*i*kuai(n,mod-2)%mod};
      |                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:84:35: warning: narrowing conversion of ‘(((long long int)((int)mod)) - (((1 * ((long lo...

Judge Result