P1641-[SCOI2010]生成字符串

雨点打透心脏的1/2处 2023-06-01 08:54 62阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 typedef double db;
     5 #define INF 0x3f3f3f3f
     6 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     7 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     8 #define mod 20100403
     9 
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 ll exgcd(ll a,ll b,ll &x,ll &y)
    26 {
    27     if(b==0)
    28     {
    29         x=1,y=0;
    30         return a;
    31     }
    32     ll res=exgcd(b,a%b,y,x);
    33     y-=a/b*x;
    34     return res;
    35 }
    36 
    37 ll Inv(ll a)
    38 {
    39     ll d,x,y;
    40     d=exgcd(a,mod,x,y);
    41     if(d==1)
    42       return (x%mod+mod)%mod;
    43     return -1;
    44 } 
    45 
    46 ll C(ll n,ll m)
    47 {
    48     ll ans1=1,ans2=1;
    49     for(int i=n,j=1;j<=m;j++,i--)
    50     {
    51         ans1=ans1*i%mod;
    52         ans2=ans2*j%mod;
    53     }
    54     return (ll)(ans1*Inv(ans2)%mod);
    55 } 
    56 ll N,M;
    57 int main()
    58 {
    59     N = read();
    60     M = read();
    61     ll a = C(N+M,M);
    62     ll b = C(N+M,M-1);
    63     printf("%lld\n",(a-b+mod)%mod);
    64     return 0;
    65 }

转载于:https://www.cnblogs.com/Asurudo/p/11475158.html

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关 P2330 [SCOI2005]繁忙的都市

题目描述城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相

╰半夏微凉°/ 2023年07月12日 01:29/ 0 赞/ 99 阅读

相关【SCOI2010】股票交易

Description [【SCOI2010】股票交易][SCOI2010] 在T天时间内，第\\(i\\)天股票购入价为\\(ap\_i\\)，出售价为\\(bp\_

落日映苍穹つ/ 2023年06月05日 08:55/ 0 赞/ 85 阅读

相关 P4180 严格次小生成树[BJWC2010]

[题目链接][Link 1] 当时在暑假早就讲了这道题了，只不过我现在才做了这道题。题解：我们要求次小生成树的话，考虑先把最小生成树求出来，因为如果我们用求最小生成树

àì夳堔傛蜴生んèń/ 2023年06月04日 07:58/ 0 赞/ 222 阅读

相关 P2573 [SCOI2012]滑雪

[题目链接][Link 1] 在题中每个点都有一个限制条件，对于一个点，只能通向高度低于它的点，所以我们可以对题目中的所有点建有向图。然后可以从1开始通过bfs找到所有可以通

短命女/ 2023年06月04日 07:58/ 0 赞/ 195 阅读

相关 P2324-[SCOI2005]骑士精神

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

今天药忘吃喽~/ 2023年06月01日 08:58/ 0 赞/ 94 阅读

相关 P2330-[SCOI2005]繁忙的都市

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

墨蓝/ 2023年06月01日 08:55/ 0 赞/ 101 阅读

相关 P2327-[SCOI2005]扫雷

1 include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll;

小鱼儿/ 2023年06月01日 08:54/ 0 赞/ 88 阅读

相关 P1641-[SCOI2010]生成字符串

1 include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll;

雨点打透心脏的1/2处/ 2023年06月01日 08:54/ 0 赞/ 63 阅读

相关 P2327 [SCOI2005]扫雷

[https://www.luogu.org/problem/show?pid=2327][https_www.luogu.org_problem_show_pid_2327]

浅浅的花香味﹌/ 2022年06月07日 14:08/ 0 赞/ 259 阅读

相关 P2324 [SCOI2005]骑士精神

[传送门][Link 1] 直接 $dfs$ 会 $T$ 飞，$BFS$ 又会爆空间考虑迭代加深搜索，枚举走的最大步数， $dfs$ 时如果步数大于枚举的步数就返回然

朱雀/ 2021年10月29日 09:30/ 0 赞/ 417 阅读