提出 #50545493

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
struct fra{ll a,b;}; // z的分割 a/b, a>0,b>0 1e6, 最简分数
bool operator <(const fra&x,const fra&y){return x.a*y.b<x.b*y.a;}
bool operator ==(const fra&x,const fra&y){return x.a==y.a and x.b==y.b;};
using linear=array<ll,2>; // {b,k}: bx^0+kx^1
linear operator-(const linear&x,const linear&y){return {x[0]-y[0],x[1]-y[1]};}
using poly=vector<mint>;
poly& operator+=(poly&p0,const poly&p1){ // 多项式加法
  if(p1.size() > p0.size()) p0.resize(p1.size());
  rep(i,0,size(p1)) p0[i]+=p1[i];
  return p0;
}
poly operator*(const poly&p0,const poly&p1){ return convolution(p0,p1); }

#define N 22
// mint dp[N][N*2][N];// [i][j][k] 前i个 和i同区间的有k个,它们在[vj..vj+1]这区间里 概率
poly g[N][N*2];// [i][j][k]=sum dp[i][j][forall] 前i个和i同区间的有任意个,它们在[vj..vj+1]这区间里z^k的系数
mint inv[N];
linear sr[N*2];
tuple<double,int,linear> fr[N*2]; // {新端点, idx +左 -右, xi-? z的0次1次系数}

int main() {
  int n=read();
  vector<int> x(n+1);
  rep(i,0,n+1) x[i]=read();
  rep(i,1,n+1) inv[i]=mint(i).inv();
  vector<fra> tp;
  auto addfrac=[&](int x,int y) { int g=gcd(x,y); tp.push_back({x/g,y/g}); };
  addfrac(0,1); // 0=0/1, 不用加无限点是因为 最右[maxz,\infity)的区间方案为0, 可以省略
  rep(i,0,n+1) rep(j,i+1,n+1) { // [xi-iz,x{i+1}-iz] [xj-jz,x{j+1}-jz]
    int dx=x[j]-x[i];
    int di=j-i;
    addfrac(dx,di); // 头对头，尾对尾
    if(di>1) addfrac(dx,di-1); // xi-iz, xj-(j-1)z
    addfrac(dx,di+1); // xi-{i-1}z, xj-jz
  }
  sort(begin(tp),end(tp),[&](const fra&a,const fra&b){return a < b;}); // 排序+去重
  tp.resize(unique(begin(tp),end(tp))-begin(tp));
  mint ans=0;
  vector<int>lb(n+1,0),rb(n+1,0); // lb[区间id]=左端点顺序idx,rb[区间id]=右端点顺序idx
  rep(i,1,size(tp)) { // tp[i-1]~tp[i] 之间的排序
    double sp=(1.0*tp[i-1].a/tp[i-1].b+1.0*tp[i].a/tp[i].b)/2; // 取区间中点 来完成排序, 也可以不用double通过双端点比较完成
    rep(j,1,n+1) { // 区间[x[j-1]-jz, x[j]-jz]的端点
      fr[j*2-1]={x[j-1]-j*sp, j,{x[j-1],-j}};
      fr[j*2-0]={x[j  ]-j*sp,-j,{x[j  ],-j}};
    }
    sort(fr+1,fr+n*2+1); // 排序所有端点
    rep(j,1,n*2+1) {
      int id=get<1>(fr[j]);
      if(id>0)lb[id]=j; // 左端点
      else rb[-id]=j;
    }
    rep(j,1,n*2) sr[j] = get<2>(fr[j+1])-get<2>(fr[j]); // 区间长度 = dx+di*z
    rep(j,0,n+1) rep(k,1,n*2+1) g[j][k] = {0}; // clear;
    g[0][0] = {1};
    //g[i][j]=(sum_{c=1..maxc}(a0+a1x)^c/c!) sum g[i-1][<j],maxc=i前最多连续?个坐标在tp[i-1..i]可选
    rep(j,1,n+1) {
      poly su = {0}; // sum g[i-1][<j]
      rep(k,1,n*2+1) { // 第j个放在 第k个端点区间
        su += g[j-1][k-1];
        poly tmp = su;
        auto [a0,a1] = sr[k]; // 区间长度的 0次系数 1次系数
        rep(l,j,n+1) {
          if(k<lb[l] or rb[l]<=k)break; // lb[l] <= k < rb[l]
          tmp = tmp * poly{a0*inv[l-j+1],a1*inv[l-j+1]}; // *(a0+a1x)/(l-j+1)
          g[l][k] += tmp; // g[l][k] += (a0+a1x)^c/c! (sum g[j-1][<k]), c=l-j+1
          assert((int)g[l][k].size() <= l+1);
        }
      }
    }
    poly su = vector<mint>(n+1,0); // su = sum g[n][<k]
    rep(k,1,n*2+1) su += g[n][k];

    mint li=mint(tp[i-1].a)/tp[i-1].b;
    mint ri=mint(tp[i].a)/tp[i].b;
    rep(k,0,n+1) ans += su[k]*(ri.pow(k+1)-li.pow(k+1))/(k+1); // \int \sum a_i x^i = \sum a_i/(i+1) x^{i+1}
  }
  rep(i,0,n) ans/=(x[i+1]-x[i]); // 统一处理分母
  printf("%d\n",ans.val());
  return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:53:31: warning: narrowing conversion of ‘j’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
   53 |       fr[j*2-1]={x[j-1]-j*sp, j,{x[j-1],-j}};
      |                               ^
Main.cpp:54:30: warning: narrowing conversion of ‘- j’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
   54 |       fr[j*2-0]={x[j  ]-j*sp,-j,{x[j  ],-j}};
      |                              ^~
Main.cpp: In function ‘ll read()’:
Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果