Wannafly挑战赛17 A&B

A 走格子

1. 暴力模拟

   const int maxn = 1e3+100;
   int vis[maxn][maxn];
   int main(void) {
   
   int n,m;
   cin>>n>>m;
   int i,j;
   i = j = 1;
   vis[1][1] = 1;
   while(m > 0){
    while(i+1 <= n&&!vis[i+1][j]&&m > 0) vis[i][j] = 1,i++,m--;
   //         cout<<i<<" "<<j<<endl; while(j+1 <= n&&!vis[i][j+1]&&m > 0) vis[i][j] = 1,j++,m--;
   //         cout<<i<<" "<<j<<endl; while(i-1 >= 1&&!vis[i-1][j]&&m > 0) vis[i][j] = 1,i--,m--;
    while(j-1 >= 1&&!vis[i][j-1]&&m > 0) vis[i][j] = 1,j--,m--;
   //        cout<<i<<" "<<j<<endl; } cout<<i<<" "<<j<<endl; //cout<<x<<" "<<y<<endl; return 0; }

B 求值2

const int maxn = 2e6+100;
// 线性求逆元
LL inv[maxn];
LL fac[maxn];
LL invfac[maxn];
void init(void) {
    LL p = mod;
    inv[1] = 1;
    int n = 2e6;
    for(int i = 2; i <= n; ++i)
        inv[i] = (p-(p/i)*inv[p%i]%p)%p;
    fac[1] = invfac[1] = 1;
    for(int i = 2;i <= n; ++i)
       fac[i] = fac[i-1]*i%p;
    for(int i = 2;i <= n; ++i)
        invfac[i] = invfac[i-1]*inv[i]%p;
}

int main(void) {
   init();

   LL n;
   cin>>n;
//   cout<<inv[n]<<endl;
//   cout<<fac[n]<<endl;
//   cout<<invfac[n]<<endl;
//   cout<<inv[3*2]<<endl;
   LL ans = 0;
   for(int i = 1;i <= n; ++i)
      {
          ans = ans + (fac[2*i]*invfac[i]%mod)*(invfac[i])%mod;
          ans %= mod;
//          cout<<i<<" "<<fac[2*i]<<" "<<invfac[i]<<endl;
//          cout<<ans<<endl;
      }
   cout<<ans<<endl;
    }