题目
题解
我写的另一种方法，复杂度是\(O(Tm+nm)\)的，这是huangzhaojun写的题解。。。
#include#include #define N 210#define mo 998244353using namespace std;int n,a,dp[N][N],A=200,fr[N];int qpow(int a,int i){ int r=1;for(;i;i>>=1,a=1ll*a*a%mo)if(i&1)r=1ll*r*a%mo;return r;}int main(){ freopen("sell.in","r",stdin); freopen("sell.out","w",stdout); int _;scanf("%d",&_); dp[0][0]=1;fr[0]=1; for(int i=1;i<=A;++i)fr[i]=1ll*fr[i-1]*i%mo; for(int i=1;i<=A;++i)for(int j=0;j<=i;++j)dp[i][j]=((j?1ll*dp[i-1][j-1]*(i-j+1):0)+dp[i-1][j])%mo; while(_--){ int ans=0; scanf("%d %d",&n,&a); for(int i=0;i<=a;++i)ans=(ans+1ll*(i%2==1?-1:1)*dp[a][i]*qpow(a-i,n-a)%mo*fr[a-i])%mo; printf("%d\n",(ans+mo)%mo); }}