Submission #36273738

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD = 998244353;
using mint = atcoder::static_modint<MOD>;

#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 N=14000000;
mint fac[N+10]={1};
mint ifac[N+10];
mint binom(int n,int m){return (m>n||m<0)?0:(fac[n]*ifac[m]*ifac[n-m]);}

int main(){
  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);

  int n=read();
  int m=read();
  mint ans =0;

  rep(s12,0,m+1){ // mod part
    mint s=0;
    rep(fi,0,3) s+=binom(n-1,s12-fi-(n-1));
    ans += s*binom(n+(m-s12)/3,n);
  }
  printf("%d\n",ans.val());
  return 0;
}

// ai [0,M]
// 单调递增
// 相邻mod3 不同
//
// f(n,m) = 范围 [0..m] n个, 第一个 == 0
// ans = sum f(n,0..m)
//
// f(n,m) = sum f(n-1,m-1..m-2..m-非3倍数)
// 
// f(n) = f(n-1) * poly(0,1,1,0,1,1,0,1,1,0,1,1,...)
//
// f(1) = (1,1,1,1,1,...
//
// f(n) = f(1) * poly(....)^{n-1}
//
//         1 1 1 1 1 1 1 1
//         0 1 2 2 3 4 4 5
// poly = x(1+x^3+x^6) + x^2(1+x^3+x^6) +...
//
// poly = (x+x^2)/(1-x^3)
// 
// (x+x^2)/(1-x^3)
// 
// 1/(1-x)^2 * [(x+x^2)/(1-x^3)]^{n-1}
// 
// 的m次方的系数
//

Submission Info

Compile Error

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

Judge Result