bc41第三题：
由 1 ～ n-1 这 n-1 个数组成 l - c 到 r - c 闭区间内的数共有多少种组合方法；
据称本来应该也比较简单吧，xiaoxin说了个五边形数，然后纷纷找了五边形数的模板，虽然并没有来得及AC，赛后交了也过了，这个东西还是要研究一下的昂，总之就是对于某个数n，用1～n组成n，每个数可以用有限多次，有多少种组合方法，本题则是只能用一次，算区间和。这样 n 只是个幌子，因为 r - c 小于等于 n - 1，然后用前缀和预处理，o（1）输出就行。
但是据说其实就是 dp 就能做，毕竟我太鱼了恩。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 8 using namespace std; 9 10 typedef long long LL; 11 const int Maxn=100010; 12 const LL MOD=998244353; 13 LL Q[Maxn],P[Maxn]; 14 LL num[Maxn]; 15 LL GetQ(LL x) 16 { 17 LL ans=(LL)x*x*3-x; 18 return (ans/2)%MOD; 19 } 20 void _init() 21 { 22 Q[0]=0; 23 for(int i=1;i<Maxn;i++) 24 { 25 if(i&1) Q[i]=GetQ(i/2+1); 26 else Q[i]=GetQ(i/2*(-1)); 27 } 28 P[0]=P[1]=1; 29 for(int i=2;i<Maxn;i++) 30 { 31 for(int j=1;;j++) 32 { 33 if(Q[j]>i) break; 34 int t=j; 35 if(t&1) t=t/2+1; 36 else t=t/2; 37 if(t&1) 38 P[i]=(P[i]+P[i-Q[j]]); 39 else 40 P[i]=(P[i]-P[i-Q[j]]); 41 if(P[i]>=MOD) P[i]%=MOD; 42 if(P[i]<0) P[i]+=MOD; 43 } 44 } 45 } 46 LL solved(LL n,LL k) 47 { 48 LL ans=0; 49 for(int i=0;;i++) 50 { 51 if(Q[i]*k>n) break; 52 int t=i; 53 if(t&1) t=t/2+1; 54 else t=t/2; 55 if(t&1) ans=(ans-P[n-Q[i]*k]); 56 else ans=(ans+P[n-Q[i]*k]); 57 if(ans>=MOD) ans%=MOD; 58 if(ans<0) ans+=MOD; 59 } 60 return ans; 61 } 62 63 void init() 64 { 65 _init(); 66 LL k=2; 67 num[0]=1; 68 for(int i=1;i<=100001;i++){ 69 num[i]=num[i-1]+solved(i,k); 70 } 71 } 72 73 int main(){ 74 init(); 75 int T; 76 while(scanf("%d",&T)!=EOF){ 77 while(T--){ 78 int n,c,l,r; 79 scanf("%d%d%d%d",&n,&c,&l,&r); 80 l-=c; 81 r-=c; 82 if(l==0)printf("%lld ",num[r]%MOD); 83 else printf("%lld ",(num[r]-num[l-1])%MOD); 84 } 85 } 86 return 0; 87 }