Submission #38936088

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
#define per(i,a,n) for (int i=n;i-->(int)(a);)
int read(){int r;scanf("%d",&r);return r;}
const int PWR=32;
mint fac[210]={1};
mint ifac[210];
mint binom[210][210];
mint downpow(int x,int y){ // x向下一共y个 prod, O(y)
  mint res=1;
  rep(i,x-y+1,x+1) res*=i;
  return res;
}
int main(){
  int n=read();
  int m=read();
  int x=read();
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  ifac[n] = fac[n].inv();
  per(i,0,n) ifac[i]=ifac[i+1]*(i+1);
  rep(i,0,n+1) rep(j,0,i+1) binom[i][j]=(j?binom[i-1][j]+binom[i-1][j-1]:1);
  // ---
  vector<mint> f(n+1,0); // f[i] = 长度i的数组, 元素 <= M, xor == X的方案数
  rep(l,1,n+1){ // O(n3 log n)
    vector dp(PWR, vector<mint>(l+1,0)); // f[高w位][和m相同的个数] 且高w位xor == x的高w位 的 个数
    dp[PWR-1][l]=1; // 默认PWR-1位0 全部都同 且满足xor == x的PWR-1位
    per(i,0,PWR-1){ // 第i bit位
      int cm=(m>>i)&1;
      int cx=(x>>i)&1;
      rep(j,0,l+1){ // i+1位 有j个和m相同
        array<mint,2> cnt = {0,0}; // l-j 个中选[奇偶] 的方案数
        rep(k,0,l-j+1) cnt[k&1]+=binom[l-j][k];
        if(cm) rep(k,0,j+1) dp[i][k]+=dp[i+1][j]*binom[j][k]*cnt[cx^(k&1)]; // j个中选k个填1,剩下的填0,在j以外的选择来保持xor == x
        else { // 第i个bit和m相同的只能填0
          int k=0; // 0个和m相同的填1
          dp[i][j]+=dp[i+1][j]*binom[j][0]*cnt[cx^(k&1)];
        }
      }
    }
    rep(j,0,l+1) f[l]+=dp[0][j];
  }
  vector odd(n+1,vector<mint>(n+1,0)); // odd[i][j] = 1...i 分成j个不区分大小位奇数非空组方案数
  vector even(n+1,vector<mint>(n+1,0)); // even[i][j] = 1...i 分成j个不区分大小位偶数非空组方案数
  odd[0][0]=even[0][0]=1;
  rep(i,1,n+1) rep(j,1,i+1) rep(k,1,i+1) { // 拆出来的大小为k
    auto &arr=((k&1)?odd:even);
    arr[i][j]+=binom[i-1][k-1]*arr[i-k][j-1]; // 为了唯一性,设这个总是包含最小元素, 所以是binom(i-1,k-1)
  }
  vector right(n+1,vector<mint>(n+1,0));
  rep(i,0,n+1) rep(j,0,n+1) rep(k,0,i+1) right[i][j]+=even[i][k]*downpow(m+1-j,k);
  vector<mint>g(n+1,0);
  g[0]=!x;
  rep(l,1,n+1){
    g[l]=f[l];
    rep(i,0,l+1) rep(j,0,min(i,l-1)+1) g[l]-=binom[l][i]*odd[i][j]*g[j]*right[l-i][j];
  }
  mint ans=0;
  rep(i,0,n/2+1) ans+=g[n-2*i]*ifac[n-2*i]*downpow(m+i,i)*ifac[i];
  printf("%d\n",ans.val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:8:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    8 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

Judge Result