提出 #20436623

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;

#define mod 998244353
struct modint{
    int x;
    modint(int o=0){x=(o+mod)%mod;}
    modint &operator = (int o){return x=(o+mod)%mod,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
    friend bool operator <(modint a,modint b){return a.x<b.x;}
};
const double eps=1e-8;
inline int dcmp(double x){
	if(fabs(x)<=eps)return 0;
	return x>0?1:-1;
}
inline int dcmp(double x,double y){return dcmp(x-y);}

struct poly{
    vector<modint>a;
    modint& operator [](int i){return a[i];}
    int size(){return a.size();}
    void resize(int n){a.resize(n);}
    void clear(){a.clear();}
    inline modint calc(modint x){
    	modint t=1,res=0;
    	For(i,0,(int)a.size()-1)res+=t*a[i],t*=x;
    	return res;
	}
	bool operator <(const poly&b)const{return a.size()<b.a.size();}
	void print(){cout<<"sz:"<<a.size()<<' ';For(i,0,(int)a.size()-1)cout<<a[i].x<<" ";puts("");}
};
poly operator +(poly a,poly b){
	int n=max(a.size(),b.size());a.resize(n),b.resize(n);
	For(i,0,n-1)a[i]+=b[i];return a;
}
poly operator -(poly a,poly b){
	int n=max(a.size(),b.size());a.resize(n),b.resize(n);
	For(i,0,n-1)a[i]-=b[i];return a;
}
poly operator *(poly a,modint b){
	int n=a.size();
	For(i,0,n-1)a[i]*=b;return a;
}
poly operator *(poly a,poly b){
	int n=a.size(),m=b.size();
	poly c; c.resize(n+m-1);
	For(i,0,n-1)For(j,0,m-1)c[i+j]+=a[i]*b[j];
	return c;
}
poly inter(poly a){
	int n=a.size()+1;a.resize(n);
	Rep(i,n,1)a[i]=a[i-1]/i;
	a[0]=0;return a;
}
#define N 22
int n,m,x[N],k;
pii a[N<<1];
double l[N],r[N];
modint res,iv[1000005];
poly f[2][N<<1][N];
vector<pair<double,modint> >v;
pair<double,poly>t[N<<1];
int len;

poly get(int i,int j){
	poly z; z.a.pb(0);
	if(!dcmp(t[j+1].fi,t[j].fi) || dcmp(t[j+1].fi,l[i])<=0 || dcmp(t[j].fi,r[i])>=0)return z;
	return (t[j+1].se-t[j].se)*iv[x[i+1]-x[i]];
}
poly DP()
{
//	For(i,1,len)cout<<t[i].fi<<' ',t[i].se.print();
	int cur=0;
	For(j,0,2*n)For(k,0,n)f[cur][j][k].clear();
	f[0][1][0].a.pb(1);
	For(i,0,n-1)
	{
		For(j,0,2*n)For(k,0,n)f[!cur][j][k].clear();
		For(j,1,len-1)
			For(k,0,n-1){
				if(!f[cur][j][k].size())continue;
		//		cout<<"get: "<<i<<' '<<j<<' ';get(i,j).print();
				f[!cur][j][k+1]=f[!cur][j][k+1]+f[cur][j][k]*get(i,j)*iv[k+1];
				f[cur][j+1][0]=f[cur][j+1][0]+f[cur][j][k];
			}
		cur^=1;
	}
	poly res;
	For(j,0,2*n)For(k,0,n)res=res+f[cur][j][k];
	return res;
}

signed main()
{
	//freopen("m","w",stdout);
	iv[1]=1;
	For(i,2,1000000)iv[i]=iv[mod%i]*(mod-mod/i);
	n=read();
	For(i,0,n)x[i]=read();
	For(i,0,n-1)a[++k]=mkp(-i,x[i]),a[++k]=mkp(-i,x[i+1]);
	v.pb(mkp(0,0)),v.pb(mkp(1000000,0));
	For(i,1,k)
		For(j,i+1,k){
			if(a[i].fi==a[j].fi)continue;
			double d=1.0*(a[j].se-a[i].se)/(a[i].fi-a[j].fi);
			if(dcmp(d)<0||dcmp(d,1e6)>0)continue;
//			printf("x:%.5lf %d %d %d %d\n",d,a[i].fi,a[j].fi,a[i].se,a[j].se);
			if(a[i].fi<a[j].fi) v.pb(mkp(d,modint(a[i].se-a[j].se)*iv[a[j].fi-a[i].fi]));
			else v.pb(mkp(d,modint(a[j].se-a[i].se)*iv[a[i].fi-a[j].fi]));
		}
	sort(v.begin(),v.end());
//	cout<<"vsz "<<v.size()<<endl;
	For(i,1,(int)v.size()-1)
	{
	//	cout<<"o:"<<i<<endl;
//		printf("%.5lf %.5lf\n",v[i-1].fi,v[i].fi);
		if(!dcmp(v[i].fi,v[i-1].fi))continue;
		double ad=(v[i].fi+v[i-1].fi)/2;
		len=0;
		For(i,0,n-1){
			l[i]=x[i]-i*ad,r[i]=x[i+1]-i*ad;
			poly F; F.resize(2);
			F[0]=x[i],F[1]=modint(-i),t[++len]=mkp(l[i],F);
			F[0]=x[i+1],t[++len]=mkp(r[i],F);
		}
		sort(t+1,t+len+1);
		poly tmp=DP();
		tmp=inter(tmp);
//		cout<<(tmp.calc(v[i].se)-tmp.calc(v[i-1].se)).x<<endl;
		res+=tmp.calc(v[i].se)-tmp.calc(v[i-1].se);
	}
	cout<<res.x;
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int read()’:
./Main.cpp:10:5: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   10 |     if(f)x=-x;return x;
      |     ^~
./Main.cpp:10:15: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   10 |     if(f)x=-x;return x;
      |               ^~~~~~
./Main.cpp: In member function ‘modint poly::calc(modint)’:
./Main.cpp:62:10: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   62 |      For(i,0,(int)a.size()-1)res+=t*a[i],t*=x;
      |          ^
./Main.cpp:2:37: note: in definition of macro ‘For’
    2 | #define For(i,a,b) for(register int i=(a);i<=(b);++i)
      |                                     ^
./Main.cpp: In member function ‘void poly::print()’:
./Main.cpp:66:46: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   66 |  void print(){cout<<"sz:"<<a.size()<<' ';For(i,0,(int)a.size()-1)cout<<a[i].x<<" ";puts("");}
      |                                              ^
./Main.cpp:2:37: note: in definition of macro ‘For’
    2 | #define For(i,a,b) for(register int i=(a);i<=(b);++i)
      |                                     ^
./Main.cpp: In function ‘poly operator+(poly, poly)’:
./Main.cpp:70:6: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   70 |  For(i,0,n-1)a[i]+=b[i];return a;
      |      ^
./Main.cpp:2:37: note: in definition of macro ‘For’
    2 | #define For(i,a,b) for(register int i=(a);i<=(b);++i)
      |                                     ^
./Main.cpp:2:20: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
    2 | #define For(i,a,b) for(register int i=(a);i<=(b);++i)
      |                    ^~~
./Main.cpp:70:2: note: in expansion of macro ‘For’
   70 |  For(i,0,n-1)a[i]+=b[i];return a;
      |  ^~~
./Main.cpp:70:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for...

ジャッジ結果