毒瘤 % 你赛

毒瘤 % 你赛

TIM 截图 20180820155437.png

题面
A.pdf
B.pdf
C.pdf
D.pdf

A.Prefix Sum

  • 写一个表就发现是杨辉三角
  • 于是裸的组合数
  • 模数是质数,用费马小定理算逆元即可。
    ```cpp

    include

    using namespace std;
    typedef long long ll;
    const ll N=5003,M=5003;
    const ll P=998244353;

ll n,m,a[N][M];

ll ksm(ll a,ll b){// 快速幂
ll res=1;
while(b){if(b&1)res=resa%P;
a=a
a%P,b>>=1;
}
return res;
}
ll c(ll a,ll b){// 组合数
if(ab;i—)res=resi%P;
for(ll i=1;i<=d;i++)fac=fac
i%P;
ll inv=ksm(fac,P-2);
return res*inv%P;
}

ll lucas(ll a,ll b){// 毫无卵用的卢卡斯
ll res=1;
while(a||b){res*=c(a%P,b%P);
a/=P,b/=P;
}
return res;
}

int main(){scanf(“%lld%lld”,&n,&m);
printf(“%lld”,lucas(m+n-1,m));
return 0;
}
```

B.Bead

  • 暴力写一个 O(n^3)DP 可以拿 20 分
  • O(n^2) 预处理区间的代价,O(n^2)DP 可以拿 70 分
  • 利用决策的单调性可以 AC

    C.Train

    哲学数据结构?

D. 监视 G 房

树形 DP


  转载请注明: Sshwy's Blog 毒瘤 % 你赛

 上一篇
毒瘤 % 你赛 -byGLX 毒瘤 % 你赛 -byGLX
毒瘤 % 你赛 -byGLX题面A.pdfB.pdfC.pdf 总结两次的比赛的小结: 勤写暴力 稳打模板 数组开大 心态不炸 A. 吉吉买铅笔 dijkstra 分别以 1,n 为源结点走两次最短路 注意输出边的时候要取最优解```c
2018.10.01
下一篇 
CF10D LCIS CF10D LCIS
题意求两个串的最长公共上升子序列。 n,m<=500 分析用 表示 A 与 B 构成的以 为结尾的 LCIS 的长度: f[i][j]=\max_{k=0}^{j-1}\{f[i-1][k]+1\}
2018.10.01
  目录