NC54842. 序列
描述
输入描述
第一行数字,接下来行,每行两个数字
输出描述
一行一个数字表示答案
示例1
输入:
2 1 3 2 4
输出:
124780545
说明:
答案为示例2
输入:
2 1 5 6 9
输出:
1
说明:
显然必然大于C++11(clang++ 3.9) 解法, 执行用时: 122ms, 内存消耗: 32536K, 提交时间: 2019-12-20 22:33:51
#include<cstdio> #include<cctype> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define gc (p1==p2&&(p2=(p1=fr)+fread(fr,1,1<<21,stdin))==p1?EOF:*p1++) using namespace std; char ch,fr[1<<21],*p1=fr,*p2=fr; bool fig; void rd(int&x) { while(!isdigit(ch=gc)&&ch^45); if(fig=ch==45)ch=gc; x=ch-48; while( isdigit(ch=gc)) x=ch-48+x*10; if(fig) x=-x; } typedef long long ll; const int N=410,mo=998244353; int n,l[N],r[N],a[N],m,f[N/2][N][N/2],s,fac[N],ivf[N],iv[N],ans; int fpow(int x,int y) {int a=1; for(;y;y>>=1,x=1ll*x*x%mo)if(y&1)a=1ll*a*x%mo; return a;} int c(int x,int i) {return l[i]<r[i]?1ll*x*iv[i]%mo:1;} int main() { rd(n); fac[0]=1; fo(i,1,n) { rd(l[i]),rd(r[i]),a[i*2-1]=l[i],a[i*2]=r[i],ivf[i]=fpow(fac[i]=1ll*fac[i-1]*i%mo,mo-2); if(l[i]<r[i]) iv[i]=fpow(r[i]-l[i],mo-2); } sort(a+1,a+2*n+1); m=unique(a+1,a+2*n+1)-a-1; fo(i,1,m-1) if(l[1]<=a[i]&&a[i+1]<=r[1]) f[1][i][1]=c(a[i+1]-a[i],1); fo(i,1,n-1) fo(k,1,i) { s=0; fo(j,1,m-1) { if(l[i+1]<=a[j]&&a[j+1]<=r[i+1]) f[i+1][j][k+1]=1ll*f[i][j][k]*c(a[j+1]-a[j],i+1)%mo; s=(s+1ll*f[i][j][k]*ivf[k])%mo; if(j<m-1&&l[i+1]<=a[j+1]&&a[j+2]<=r[i+1]) f[i+1][j+1][1]=(f[i+1][j+1][1]+1ll*s*c(a[j+2]-a[j+1],i+1))%mo; } } fo(j,1,m-1) fo(k,1,n) ans=(ans+1ll*f[n][j][k]*ivf[k])%mo; printf("%d",ans); }