nowcoder contest10

nowcoder contest10

D 推公式

有下面的操作:

  1. 区间[l, r]进行+w的操作
  2. [1, n]区间每一个点更新为前缀和
  3. 查询区间[l, r]区间的和

进行操作3的时候:求每一个\(w_i\)对一个查询点的贡献

前缀对一个点的值的贡献为组合数

同一模型

一个人跳k次到达x坐标,每一次都可以往前跳任意单位(可以是0个单位)
问方案数?

解答

问题转化为\(x_1+x_2+x_3+\dots + x_n = x, x_i \ge 0\), 转化为$y_1+y_2+y_3+\dots + y_n=x+n, y_i \ge 1$

然后用隔板法求解就可以了:$ C_{x+n-1}^{n-1}$

有下面的公式:
sum[i][j]表示的是下标为i,j为进行操作2的次数,那么每个\(w_i\)的贡献就可以这样的统计
sum[i][j] = sum[i-1][j-1]+sum[i-1][j]

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll fac[310000],inv[310000];
ll C(int n,int m)
{
ll res=fac[n]*inv[m]%mod*inv[n-m]%mod;
return res;
}
struct node
{
int l,r,w,id;
}a[210000];
int now;
int n,m,nn;
ll cc(int x,ll w,int id,int y)
{
if (x>y) return 0;
return w*C(id+1+y-x,y-x)%mod;
}
ll cal(int x)
{
ll res=0;
for (int i=1;i<=nn;i++)
if (a[i].l<=x){
int tmp=now-a[i].id;
ll par1 = cc(a[i].l,a[i].w,tmp,x)-cc(a[i].r+1, a[i].w,tmp,x);
while(par1<0) par1 += mod;
res=(res+par1+mod)%mod;
}
return res;
}
int main()
{
fac[0]=1;
for (int i=1;i<=210010;i++)
fac[i]=(fac[i-1]*i)%mod;
inv[1]=inv[0]=1;
for (int i=2;i<=210010;i++)
{
inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
}
for (int i=2;i<=210010;i++)
inv[i]=(inv[i-1]*inv[i])%mod;
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d %d",&n,&m);
now=nn=0;
while (m--)
{
int op;
scanf("%d",&op);
if (op==1)
{
int l,r,w;
scanf("%d %d %d",&l,&r,&w);
a[++nn]={l,r,w,now};
}
else if (op==2) now++;
else
{
int l,r;
scanf("%d %d",&l,&r);
ll ans=(cal(r)-cal(l-1)+mod)%mod;
printf("%lld\n",ans);
}
}
}
return 0;
}

第九场的H

和上面非常像的一个题目,但是就按照上面的做法写,就会T

T代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 1e5+10;
typedef long long ll;
ll fac[maxn], inv[maxn];
int n, m, k, x, y;
int nn;
void init(){
fac[0]=1;
for (int i=1;i<maxn;i++)
fac[i]=(fac[i-1]*i)%mod;
inv[1]=inv[0]=1;
for (int i=2;i<maxn;i++)
{
inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
}
for (int i=2;i<maxn;i++)
inv[i]=(inv[i-1]*inv[i])%mod;
}
struct Node{
int x, id;
bool operator < (Node b)const{
return x<b.x;
}
}node[maxn];
ll pow_mod(ll a, ll b){
ll ans = 1;
while(b){
if(b&1) ans = ans*a%mod;
b>>1;
a = a*a%mod;
}
return ans;
}
ll C(int n, int m){
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll cc(int x, int y, ll w){
if(x>y) return false;
//cout<<"test"<<y-x+k-1<<" "<<w<<endl;
return C(y-x+k-1, y-x)*w%mod;
}
multiset<Node>::iterator it;
multiset<Node> s;
ll query(int x){
ll ans = 0;
for(it=s.begin(); it!=s.end(); it++){
//cout<<"huhu"<<(*it).x<<endl;
if((*it).x>x) break;
else{
ans += cc((*it).x, x, (ll)(*it).id);
ans = ans%mod;
}
}
return ans;
}
int main()
{
init();
while(~scanf("%d%d%d", &n, &m, &k)){
int op;
s.clear();
nn = 0;
for(int i=0; i<m; i++){
scanf("%d", &op);
if(op == 0){
scanf("%d%d", &x, &y);
s.insert(Node{x, y});
}
else if(op == 1){
scanf("%d", &x);
printf("%lld\n", query(x));
}
}
}
return 0;
}

正解

类欧几里得

未解决的问题

文章目录
  1. 1. D 推公式
    1. 1.1. 同一模型
    2. 1.2. 解答
    3. 1.3. ac code
  2. 2. 第九场的H
    1. 2.1. T代码
    2. 2.2. 正解
  3. 3. 类欧几里得
  4. 4. 未解决的问题
{{ live2d() }}