G47 斯特林反演

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1006
int n, x, P, m;
int a[N],S[N][N],J[N],pw[N],pw1[N];

int qpow(int a, int b){
  int res=1;
  while(b){
      if(b&1)res=1ll*res*a%P;
      a=1ll*a*a%P; b>>=1;
  }
  return res;
}
int main(){
  cin >> n >> x >> P >> m;
  for(int i=0; i<=m; ++i)scanf("%d",a+i);
  
  S[0][0]=1;
  for(int i=1; i<=m; ++i)
      for(int j=1; j<=i; ++j)
        S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j]%P)%P;
  J[0]=1;
  for(int i=1; i<=m; ++i)
      J[i]=1ll*J[i-1]*(n-i+1)%P;
  for(int i=0; i<=m; ++i)
      pw[i]=qpow(x, i), pw1[i]=qpow(x+1, n-i);
      
  int ans=0;
  for(int i=0; i<=m; ++i){
      int sum=0;
      for(int j=0; j<=i; ++j)
        sum=(sum+1ll*S[i][j]*J[j]%P*pw[j]%P*pw1[j])%P;
      ans=(ans+1ll*a[i]*sum)%P;
  }
  cout << ans << endl;
}

G47 斯特林反演

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1006
int n, x, P, m;
int a[N],S[N][N],J[N],pw[N],pw1[N];

int qpow(int a, int b){ int res=1; while(b){ if(b&1)res=1llresa%P; a=1llaa%P; b>>=1; } return res; } int main(){ cin >> n >> x >> P >> m; for(int i=0; i<=m; ++i)scanf("%d",a+i);

S[0][0]=1; for(int i=1; i<=m; ++i) for(int j=1; j<=i; ++j) S[i][j]=(S[i-1][j-1]+1lljS[i-1][j]%P)%P; J[0]=1; for(int i=1; i<=m; ++i) J[i]=1llJ[i-1](n-i+1)%P; for(int i=0; i<=m; ++i) pw[i]=qpow(x, i), pw1[i]=qpow(x+1, n-i);

int ans=0; for(int i=0; i<=m; ++i){ int sum=0; for(int j=0; j<=i; ++j) sum=(sum+1llS[i][j]J[j]%Ppw[j]%Ppw1[j])%P; ans=(ans+1ll*a[i]*sum)%P; } cout << ans << endl; }</pre>