首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Codeforces 的题目真的值得算法竞赛选手训练吗?

Codeforces 的题目真的值得算法竞赛选手训练吗?

作者头像
ACM算法日常
发布2021-11-10 16:44:01
发布2021-11-10 16:44:01
97800
代码可运行
举报
文章被收录于专栏:ACM算法日常ACM算法日常
运行总次数:0
代码可运行

今天我们要来看看 Codeforces 2016-2017 年的一套训练题。

2016-2017 CT S03E07: Codeforces Trainings Season 3 Episode 7 - HackerEarth Problems Compilation

题目链接:https://codeforces.com/gym/101138

Problem A

题意:给

n

个串,有两种操作,一种是给某个串加一个字符,另一种是求存不存在一个串是查询串的子串。强制在线。

题解:由于限制了总长,所以不同的长度不会太多(根号级别)。枚举长度匹配一下哈希就行。

自动机也是能搞的,但是没有hash写起来舒服。

代码语言:javascript
代码运行次数:0
运行
复制
#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long
ll input(){
 ll x=0,f=0;char ch=getchar();
 while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
 while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
 return f? -x:x;
}

#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair

const ll base=37;
const int N=8e5+7;

char s[N];

int last_ans;
map<int,int> len;
multiset <ll> S;
ll p[N];
int lc[N];
ll Base[N],qu[N];

ll hsh(char *s){
 ll ret=0;
 int le=strlen(s);
 for(int i=le-1;i>=0;i--){
  ret=ret*base+s[i]-'a';
 }
 return ret;
}

bool match(char *s){
 int le=strlen(s);
 qu[le]=0;
 for(int i=le-1;i>=0;i--){
  qu[i]=qu[i+1]*base+(s[i]-'a'+last_ans)%26;
 }
 for(auto v:len){
  int l=v.fr;
  for(int i=0;i<le-l+1;i++){
   ll tmp=qu[i]-qu[i+l]*Base[l];
   if(S.find(tmp)!=S.end()) return 1;
  }
 }
 return 0;
}

int main(){
 Base[0]=1;
 for(int i=1;i<N;i++) Base[i]=Base[i-1]*base;

 int n=input(),q=input();

 for(int i=0;i<n;i++){
  scanf("%s",s);
  p[i]=hsh(s);
  lc[i]=strlen(s);
  len[lc[i]]++;
  S.insert(p[i]);
 }

 for(int i=0;i<q;i++){
  int f=input();
  if(f==1){
   scanf("%s",s);
   if(match(s)){
    printf("YES\n");
    last_ans=i;
   }else{
    printf("NO\n");
   }
  }else{
   int pos=input(),alpha=input();
   pos=(pos+last_ans)%n;
   alpha=(alpha+last_ans)%26;
   ll tmp=p[pos]+alpha*Base[lc[pos]];
   S.erase(S.find(p[pos]));S.insert(p[pos]=tmp);
   if(len[lc[pos]]==1) len.erase(lc[pos]);
   else len[lc[pos]]--;
   len[++lc[pos]]++;
  }
 }
}

Problem B

温暖的签到题。

代码语言:javascript
代码运行次数:0
运行
复制
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=105;
char s[maxn];
int main(){
    int tt;
    int i,n,m;
    bool can;
    scanf("%d",&tt);
    while (tt--){
        scanf("%s",s);
        m=n=strlen(s);
        while (!(m&1)) m/=2;
        if (m!=1){
            puts("NO");
            continue;
        }
        can=true;
        if (n==1){
            puts("YES");
            continue;
        }
        for (i=0;i<n;i+=2){
            if (s[i]!='P'&&s[i+1]!='P')
                can=false;
        }
        puts(can?"YES":"NO");
    }
    return 0;
}

Problem C

题意:给定一个没有重边的图,求此图中一共有多少给定火柴人形状的子图。

题解:观察这个火柴人,我们发现七个点中,其他五个点都连在剩下的两个点上。因此,枚举中间相连的两个点,接下来分别判断它们分别是上半身和下半身中点的情况。

对于剩下所有的点,有四种情况:两个点都不连接,连接上半身的点,连接下半身的点,和两个都连接。

对于第一种情况,无需讨论。对于第二种情况,只要讨论下半身的剩下两个点在后两种情况中怎么取,就可以求出方案数。对所有方案数求和就是答案。

代码语言:javascript
代码运行次数:0
运行
复制
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=205,mod=1e9+7;
int a[maxn][maxn];
int b[maxn];
ll c[maxn][maxn];
int n;
void sear(int u,int v,ll &cnt1,ll &cnt2,ll &cnt3){
    int i;
    cnt1=cnt2=cnt3=0;
    memset(b,0,sizeof(b));
    for (i=1;i<=n;i++) if (i!=u&&i!=v){
        if (a[u][i]&&a[v][i]) cnt2++;
        else if (a[u][i]) cnt1++;
        else if (a[v][i]) cnt3++;
    }
}
ll solve(ll x,ll y,ll z){
    ll ans=0;
    if (z>=2&&x+y>=3) ans=(ans+c[z][2]*c[x+y][3]%mod)%mod;
    if (z>=1&&x+y>=4&&y>=1) ans=(ans+z*y%mod*c[x+y-1][3]%mod)%mod;
    if (x+y>=5&&y>=2) ans=(ans+c[y][2]*c[x+y-2][3]%mod)%mod;
    return ans;
}
int main(){
    int i,j,m;
    int u,v;
    ll cnt1,cnt2,cnt3;
    ll ans;
    scanf("%d%d",&n,&m);
    memset(c,0,sizeof(c));
    for (i=0;i<=n;i++) c[i][0]=c[i][i]=1;
    for (i=1;i<=n;i++) for (j=1;j<i;j++)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    memset(a,0,sizeof(a));
    for (i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        a[u][v]=1; a[v][u]=1;
    }
    ans=0;
    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
        if (a[i][j]){
            sear(i,j,cnt1,cnt2,cnt3);
            ans+=solve(cnt1,cnt2,cnt3);
            ans%=mod;
        }
    cout<<ans<<endl;
    return 0;
}

Problem D

题意:给出

m

个询问,每个询问给出

l_1,l_2,r_1,r_2

,求由多少个二元组

(i,j)

使得

l_1<=i<=r_1,l_2<=j<=r_2,a_i=a_j

题解:从

f(l_1,r_1,l_2,r_2)

f(l_1+1,r_1,l_2,r_2)

等曼哈顿距离为1的询问是可以

O(1)

转移的,加上或者减去改变的数作为二元组其中一个点即可。然而四维还不能直接使用莫队,需要用容斥转化成二维查询。

dp[i][j]

表示

1

i

1

j

两个区间的询问,则

solve(l_1,r_1,l_2,r_2)=dp[r_1][r_2]-dp[l_1-1][r_2]-dp[r_1-1][l_2]+dp[l_1-1][l_2-1]

代码语言:javascript
代码运行次数:0
运行
复制
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e4+5;

typedef long long ll;
typedef long long LL;
struct query {
    int l, r, ord, sgn;
} que[MAXN*4];

const int base=230;

bool operator < (query a,query b){
    if (a.l/base!=b.l/base) return a.l/base<b.l/base;
    if ((a.l/base)&1) return a.r<b.r;
    else return a.r>b.r;
}

int ans_size;


ll ans[MAXN*4];

int n, m, a[MAXN];

vector<int> pos[MAXN];

LL calc(int x, int l, int r) {
    int ll = lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin();
    if (pos[x][ll] == n+1) return 0;
    int rr = lower_bound(pos[x].begin(), pos[x].end(), r+1) - pos[x].begin() - 1;
    if (rr < 0) return 0;
    return rr-ll+1;
}

LL init(int l, int r) {
    LL ans = 0;

    for (int i=1; i<=n; ++i) {
        ans += calc(i, 1, l) * calc(i, 1, r);
    }
    return ans;
}

LL addl(int l, int r) {
    return calc(a[l+1], 1, r);
}

LL addr(int l, int r) {
    return calc(a[r+1], 1, l);
}

LL minusl(int l, int r) {
    return -calc(a[l], 1, r);
}

LL minusr(int l, int r) {
    return -calc(a[r], 1, l);
}

void solve(){
    int i,l,r;
    ll anss;
    sort(que,que+ans_size);
    anss=init(1,1); l=r=1;
    for (i=0;i<ans_size;i++){
        while (r<que[i].r){
            anss+=addr(l,r); r++;
        }
        while (l>que[i].l){
            anss+=minusl(l,r); l--;
        }
        while (r>que[i].r){
            anss+=minusr(l,r); r--;
        }
        while (l<que[i].l){
            anss+=addl(l,r); l++;
        }
        ans[que[i].ord] += que[i].sgn*anss;
    }
}


int main() {

//    freopen("in.txt", "r", stdin);

    scanf("%d", &n);

    for (int i=1; i<=n; ++i) {
        scanf("%d", &a[i]);
        pos[a[i]].push_back(i);
    }

    for (int i=1; i<=n; ++i) {
        pos[i].push_back(n+1);
    }

    scanf("%d", &m);
    ans_size = 0;
    for (int i=0; i<m; ++i) {
        int l[2], r[2];
        scanf("%d%d%d%d", &l[0], &r[0], &l[1], &r[1]);
        que[ans_size++] = (query){r[0], r[1], i, 1};
        que[ans_size++] = (query){l[0]-1, r[1], i, -1};
        que[ans_size++] = (query){r[0], l[1]-1, i, -1};
        que[ans_size++] = (query){l[0]-1, l[1]-1, i, 1};
    }

    solve();
    for (int i=0; i<m; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}

Problem E

题意:给第一匹马找一个匹配,询问是否存在第一匹马的匹配代价大于其他所有的匹配。

题解:贪心。显然给第一匹马找最大的匹配。

其余的肯定是最大的和最小的匹配,依此类推。

直接排序,暴力判断即可。

代码语言:javascript
代码运行次数:0
运行
复制
#include<bits/stdc++.h>

using namespace std;

int T,n,m,w[100],h[100];

bool cmp(int x,int y)
{
    return x>y;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&h[i]);
        sort(h+1,h+1+n,cmp);
        sort(w+2,w+1+n);
        int ans=h[1]*w[1];
        for (int i=2;i<=n;i++)
            if (h[i]*w[i]>=ans) ans=-1;
        if (ans==-1) puts("NO");else puts("YES");
    }
    return 0;
}

Problem F

题意:

f_i = f_{i-1} + a_{i \bmod n}

,

f_0 = 0

;

g_n = h - \frac{n(n+1)}{2}

。求第一个

n

满足

f_n \ge g_n

题解:

f_i

分别变成

f_i+i

可以在保证

|f_i-g_i|

不变的情况下,把

g_i

矫正成直线。题目变成询问

f_i

的前缀和第一个超过常数

g

的位置。

二分判断在哪一个周期超过了常数

g

,判断的方法是找一个周期的最高点。

对于第

x

个周期,前

x-1

个周期的前缀和可以直接得到,然后暴力计算本周期的前缀和,判断最大的是否超过了常数

g

对于第一个超过的周期,暴力寻找位置即可。

这道题目会爆long long,然后各种玄学的方法来调整判断,于是自闭了。

代码语言:javascript
代码运行次数:0
运行
复制
#include <bits/stdc++.h>
using namespace std;
#define LL long long

int n;
LL m,a[100010],b[100010];

bool check(LL x)  //x >=m
{
    double y=0.0;
    for (int i=1;i<=n;i++)
        y+=(((double)a[i])+((double)i))*((double)x)+((double)x)*(((double)x)-1.0)/2.0*((double)n);
    if (y>((double)m)*100000000.0) return true;
    if (y<((double)m)*(-100000000.0)) return false;
    LL ans=0;
    for (int i=1;i<=n;i++)
    {
        if (((double)a[i])+((double)i)+((double)(n)*(double)(x))>((double)m)*100000000.0) return true;
        if (((double)a[i])+((double)i)+((double)(n)*(double)(x))<((double)m)*(-100000000.0)) return false;
        b[i]=(a[i]+((LL)i)+((LL)(n)*(x)));
        ans+=(a[i]+((LL)i))*x+x*(x-1LL)/2LL*(LL)n;
    }
    for (int i=1;i<=n;i++)
    {
        if (((double)b[i])+((double)ans)>((double)m)*100000000.0) return true;
        if (((double)b[i])+((double)ans)<((double)m)*(-100000000.0)) return false;
        if (b[i]+ans>=m) return true;
        else ans+=b[i];
    }
    return false;
}

LL solve()
{
    LL ans=0,res=m;
    for (int i=1;i<=500*n;i++)
    {
        ans+=a[(i-1)%n+1];
        res-=(LL)i;
        if (ans>=res) return (LL)i;
    }
    return -1;
}

int main()
{
    scanf("%d%I64d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%I64d",&a[i]);
    LL x=solve();
    if (x!=-1)
    {
        printf("%I64d\n",x);
        return 0;
    }
    LL l=0,r=300000000000LL,mid,res;
    while(l<=r)
    {
        mid=l+r>>1;
        if (check(mid)) res=mid,r=mid-1;
            else l=mid+1;
    }
    LL ans=res*n,s=0;
    for (int i=1;i<=n;i++)
        s+=(a[i]+((LL)i))*res+res*(res-1LL)/2LL*(LL)n;
    if (s>=m) {printf("%I64d\n",ans);return 0;}
    //cout<<res<<" "<<s<<endl;
    for (int i=1;i<=n;i++)
    {
        a[i]=(a[i]+((LL)i)+((LL)(n)*(res)));
        ans++;s+=a[i];
        if (s>=m) break;
    }
    printf("%I64d\n",ans);
    return 0;
}

Problem I

题意:给出两个素数

a,b

(

a,b\le 10^{15}

),求出只包含加减运算的的运算步骤,且中间值和加或减的数均为素数。

题解:奇数加奇数为偶数,而只有2不是奇数,所以运算的情况是相当少的。同时一个数最多加2两次,否则

x,x+2,x+4

模3的值均不同,有一个一定不是素数。如果一个数是奇数,则它只能加减2,或者是减到2。如果一个数是2,则它可以加或减到b-4~b+4。判素数应该使用Miller-Rabin,由于之前没怎么用过就被红书的板子坑了(大概是素数没选对,数据会卡。

代码语言:javascript
代码运行次数:0
运行
复制
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6+5;

typedef long long LL;

LL a, b;

const LL m=7, aa[m]={2, 3, 5, 7, 11, 13, 17};
LL n, p;

LL fmul(LL a, LL b, LL p){  //将b分解为二进制,返回a*b%p
    LL ans=0;
    for (; b; b>>=1, a+=a, a%=p)
        if (b&1) ans+=a, ans%=p;
    return ans;
}

LL fpow(LL a, LL x, LL p){
    LL ans=1, base=a;
    for (; x; x>>=1, base=fmul(base, base, p))
        if (x&1) ans=fmul(ans, base, p);
    return ans;
}

bool MR(LL a, LL x, LL p){
    LL t=fpow(a, x, p);
    if (t!=1&&t!=p-1) return false;
    if (t==1&&x&1||t==p-1) return true;
    return MR(a, x>>1, p);
}

bool isPrime(LL p){
    if (p < 2) return false;
    if (p == 2) return true;
    if (p&1==0) return false;
    for (LL i=0; i<m; ++i){
        if (p==aa[i]) return true;
        if (fpow(aa[i], p-1, p)!=1) return false;
        if (!MR(aa[i], (p-1)>>1, p)) return false;
    }
    return true;
}


struct node {
    int fa, step;
    LL v;
    node(int fa, LL v, int step):fa(fa), v(v), step(step){}
    node(){}
} que[MAXN];

int st, ed;
vector<LL> ans;

map<LL, int> mp;

bool valid(LL v, int step) {
    if (!mp.count(v) || mp[v] >= step) {
        return true;
    }
    return false;
}

int bfs(LL s, LL t) {
    st = ed = 0;
    que[ed++] = node(-1, s, 0);
    int found = -1;
    mp.clear();
    mp[s] = 0;
    while (st < ed) {
        node now = que[st];
        if (found != -1 && now.step > found) return 1;
        if (now.v == t) {
            if (found == now.step) return -1;
            found = now.step;
            int id = st;
            while (id != -1) {
                ans.push_back(que[id].v);
                id = que[id].fa;
            }
            ++st;
            continue;
        }
        if (now.v % 2) {
            LL nextv = now.v+2;
            if (valid(nextv, now.step+1) && isPrime(nextv)) {
                mp[nextv] = now.step+1;
                que[ed++] = node(st, nextv, now.step+1);
            }
            nextv = now.v-2;
            if (valid(nextv, now.step+1) && isPrime(nextv)) {
                que[ed++] = node(st, nextv, now.step+1);
                mp[nextv] = now.step+1;
            }
        } else {
            for (LL j=t-4; j<=t+4; j+=2) {
                if (valid(j, now.step+1) && isPrime(j) && (isPrime(j-now.v) || isPrime(now.v-j))) {
                    mp[j] = now.step+1;
                    que[ed++] = node(st, j, now.step+1);
                }
            }
        }


        if (valid(2, now.step+1) && isPrime(now.v-2)) {
            mp[2] = now.step+1;
            que[ed++] = node(st, 2, now.step+1);
        }

        st++;
    }
    if (found != -1) return 1;
    else return 0;
}

int main() {

    cin >> a >> b;
    int suc = bfs(a, b);
    if (suc == 1) {
        int sz = ans.size();
        printf("%I64d", ans[sz-1]);
        for (int i=sz-2; i>=0; --i) {
            printf("->%I64d",ans[i]);
        }
        putchar('\n');
    } else if (suc == 0) {
        puts("Unlucky Benny");
    } else puts("Poor Benny");
    return 0;
}

Problem J

题意:给定一棵树,每一个节点上有一个或正或负权值,现在每次访问两个节点,问这两个节点路径上的点权和最大的非空子路径的点权和是多少。

题解:

LCA

。用倍增法维护并合并一条竖直方向路径的三个元素:含有顶节点的最大子路径点权和,含有底节点的最大子路径点权和,和普通的最大子路径点权和,最后再合并两条从访问节点出发到其

LCA

的向上路径。

代码语言:javascript
代码运行次数:0
运行
复制
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
const long long inf = 1e18;

int n, Q, u, v;
long long a[maxn];
struct Edge {int to, nex;} edge[maxn << 1];
int head[maxn], ecnt;
void add_edge (int u, int v) {edge[++ecnt] = {v, head[u]}; head[u] = ecnt;}
int father[maxn], hson[maxn], siz[maxn], depth[maxn];
int cnt, dfn[maxn], rk[maxn], top[maxn];

#define ls rt << 1
#define rs rt << 1 | 1
struct node {long long sum, pre, suf, maxsum;} tr[maxn << 2], p[maxn], None = {0, -inf, -inf, -inf};
node operator + (node a, node b){
    return{
        a.sum + b.sum,
        max (a.pre, a.sum + b.pre),
        max (a.suf + b.sum, b.suf),
        max (a.suf + b.pre, max (a.maxsum, b.maxsum))
    };
}
void build (int rt, int l, int r)
{
    if (l == r) {tr[rt] = {a[rk[l]], a[rk[l]], a[rk[l]], a[rk[l]]}; return;}
    int mid = (l + r) >> 1;
    build (ls, l, mid);
    build (rs, mid + 1, r);
    tr[rt] = tr[ls] + tr[rs];
}
node query (int nl, int nr, int l = 1, int r = n, int rt = 1)
{
    if (nl > r || nr < l) return None;
    if (nl <= l && nr >= r) return tr[rt];
    int mid = (l + r) >> 1;
    node ret = query(nl, nr, l, mid, ls) + query(nl, nr, mid + 1, r, rs);
    return ret;
}

void get_hson (int now, int fa)
{
    father[now] = fa;
    siz[now] = 1;
    depth[now] = depth[fa] + 1;
    int it = 0;
    for (int i = head[now]; i; i = edge[i].nex)
    {
        int to = edge[i].to;
        if (to == fa) continue;
        get_hson (to, now);
        siz[now] += siz[to];
        if (siz[to] > siz[it]) {hson[now] = to; it = to;}
    }
}
void dfs (int now, int thetop)
{
    top[now] = thetop;
    dfn[now] = ++cnt;
    rk[dfn[now]] = now;
    if (siz[now] == 1) return;
    dfs (hson[now], thetop);
    for (int i = head[now]; i; i = edge[i].nex)
    {
        int to = edge[i].to;
        if (to == father[now] || to == hson[now]) continue;
        dfs (to, to);
    }
}
long long path_max (int u, int v)
{
    node nou = None, nov = None;
    while (top[u] != top[v])
    {
        if (depth[top[u]] < depth[top[v]]) {swap (u, v); swap(nov, nou);}
        nou = p[u] + nou;
        u = father[top[u]];
    }
    if (depth[u] > depth[v]) {swap (u, v); swap(nou, nov);}
    nov = query(dfn[u], dfn[v]) + nov;
    long long ret = max (max (nou.maxsum, nov.maxsum), nou.pre + nov.pre);
    return ret;
}

int main()
{
    //freopen("C:/Users/MACHENIKE/Desktop/data.in","r",stdin);
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    get_hson(1, 0);
    dfs(1, 1);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) p[i] = query(dfn[top[i]], dfn[i]);
    scanf("%d", &Q);
    while (Q--)
    {
        scanf("%d %d", &u, &v);
        printf("%lld\n", path_max(u, v));
    }
    return 0;
}

                               

Problem K

题意:有一列长度为

n

的火车,求一共有多少种

k

个颜色的染色方案,使得恰好有

t

种方案选出长度为

d

的颜色相同的一段车厢。

题解:首先,我们发现,如果一共有

l

段相同颜色段,一个染色方案的选出车厢的方案数为

\sum_{i=1}^{l} length_i

我们设

dp[i][k]

代表第

i

个车厢结尾有

k

种方案选出的染色数,我们发现,除了只有一段的情况,

dp[i][k]=\sum_{j=1}^{d-1} dp[i-j][k]+\sum_{j=1}^{k} dp[i-d+1-j][k-j]

。我们发现,这是一段折线段,而拐点所在列是

i-d+1

。因此,我们每次处理一列

i

,之后将拐点列上的

dp

元素从平线加到斜线上,即可在

O(n*t)

的时间内求出答案。

代码语言:javascript
代码运行次数:0
运行
复制
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=4e3+5;
const ll mod=1e9+7;
ll dp[maxn][maxn];
ll sum1[maxn],sum2[maxn];
int main(){
    int i,j,n,d,t,k;
    ll ans;
    scanf("%d%d%d%d",&n,&d,&t,&k);
    memset(dp,0,sizeof(dp));
    memset(sum1,0,sizeof(sum2));
    memset(sum2,0,sizeof(sum2));
    for (i=1;i<=n;i++){
        for (j=0;j<=t;j++){
            if (j==max(i-d+1,0)) dp[i][j]+=k;
            dp[i][j]+=sum1[j]*(k-1)%mod;
            if (i-j-d+1>=0) dp[i][j]+=sum2[i-d-j+1]*(k-1)%mod;
            dp[i][j]%=mod;
            sum1[j]=(sum1[j]+dp[i][j])%mod;
            if (i-d+1>=0) sum1[j]=(sum1[j]-dp[i-d+1][j])%mod;
            if (i-d-j+1>=0) sum2[i-d-j+1]=(sum2[i-d-j+1]+dp[i-d+1][j])%mod;
        }
    }
    cout<<((dp[n][t]+mod)%mod+mod)%mod<<endl;
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-11-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2016-2017 CT S03E07: Codeforces Trainings Season 3 Episode 7 - HackerEarth Problems Compilation
  • Problem A
  • Problem B
  • Problem C
  • Problem D
  • Problem E
  • Problem F
  • Problem I
  • Problem J
  • Problem K
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档