codeforces div 313-白红宇

codeforces div 313

阅读量：4973 次

发布时间：2019-06-12

本文共 3713 字，大约阅读时间需要 12 分钟。

C题

思路：补全三角形之后减去三个角的个数和

锁了代码一看人家，就写了三行。。

公式： (f + a + b)^2 - b^2 - f^2 - d^2

D题

忧伤。。本来觉得直接递归模拟会T，结果姿势正确还可以过。。

标程思路：化成字典序最小的串然后比较。。

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/23 8:02:58*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     20 #define INF 0x3f3f3f3f21 #define eps 1e-822 #define pi acos(-1.0)23 #define MAXN 111024 #define OK cout << "ok" << endl;25 #define o(a) cout << #a << " = " << a << endl26 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl27 using namespace std;28 typedef long long LL;29 30 string smallest(string s) {31 if (s.length() % 2 == 1) return s;32 string s1 = smallest(s.substr(0, s.length()/2));33 string s2 = smallest(s.substr(s.length()/2, s.length()));34 if (s1 < s2) return s1 + s2;35 else return s2 + s1;36 }37 38 int main()39 {40 //freopen("data.in","r",stdin);41 //freopen("data.out","w",stdout);42 cin.tie(0);43 ios::sync_with_stdio(false);44 string a, b;45 cin >> a >> b;46 a = smallest(a);47 b = smallest(b);48 if (a == b) cout <<"YES" << endl;49 else cout << "NO" << endl;50 return 0; 51 }

View Code

E题

题意:从h*w的格子，从左上角（1，1）走到右下角（h, w），要求不能经过给出的几个黑格子，求有多少种可能。

组合数+逆元搞一下。。

这个 %= ， +=，真是6。。。

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/23 9:08:32*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     20 #define INF 0x3f3f3f3f21 #define eps 1e-822 #define pi acos(-1.0)23 #define MAXH 20001024 #define MAXN 201025 #define OK cout << "ok" << endl;26 #define o(a) cout << #a << " = " << a << endl27 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl28 using namespace std;29 typedef long long LL;30 const int mod = 1e9 + 7;31 32 struct Point {33 int x, y;34 bool operator<(const Point &ss) & {35 return x + y < ss.x + ss.y; 36 }37 }p[MAXN];38 LL fac[MAXH], inv[MAXH];39 LL f[MAXN];40 41 inline LL FastPow(LL a, LL b) 42 {43 LL res = 1;44 while (b) {45 if (b&1) (res *= a) %= mod;46 (a *= a) %= mod;47 b >>= 1;48 }49 return res;50 }51 52 LL Calc(int a, int b)53 {54 return (((fac[a+b-2]*inv[a-1])%mod)*inv[b-1])%mod;55 }56 int h, w, n, mx;57 58 int main()59 {60 //freopen("data.in","r",stdin);61 //freopen("data.out","w",stdout);62 cin.tie(0);63 ios::sync_with_stdio(false);64 cin >> h >> w >> n;65 for (int i = 1;i <= n; ++ i)66 cin >> p[i].x >> p[i].y;67 p[++n] = (Point){h, w};68 mx = h + w;69 sort(p+1, p + 1 + n);70 fac[0] = inv[0] = 1;71 for (int i = 1;i <= mx; ++ i)72 fac[i] = (fac[i-1]*(LL)i)% mod;73 for (int i = 1;i <= mx; ++ i)74 inv[i] = FastPow(fac[i], mod-2);75 76 for (int i = 1;i <= n; ++ i) {77 f[i] = Calc(p[i].x, p[i].y);78 for (int j = 1;j < i; ++ j) 79 if (p[j].x <= p[i].x && p[j].y <= p[i].y)80 {81 f[i] -= f[j]*Calc(p[i].x - p[j].x + 1, p[i].y - p[j].y + 1)%mod;82 ((f[i] %= mod) += mod) %= mod;83 }84 } 85 cout << f[n] << endl;86 return 0;87 }

View Code

附：

求 a / b = x (mod M)

只要 M 是一个素数，而且 b 不是 M 的倍数，就可以用一个逆元整数 b’，通过 a / b = a * b' (mod M)，来以乘换除。

费马小定理说，对于素数 M 任意不是 M 的倍数的 b，都有：

b ^ (M-1) = 1 (mod M)

于是可以拆成：

b * b ^ (M-2) = 1 (mod M)

于是：

a / b = a / b * (b * b ^ (M-2)) = a * (b ^ (M-2)) (mod M)

也就是说我们要求的逆元就是 b ^ (M-2) (mod M)

！

转载于:https://www.cnblogs.com/usedrosee/p/4669899.html

你可能感兴趣的文章

BZOJ 1529 [POI2005]ska Piggy banks：并查集

查看>>

java多态与异常处理——动手动脑

查看>>

软件测试技术HW03-printPrimes()

查看>>

SQL Server2008附加数据库之后显示为只读时解决方法

JQuery UI datepicker 使用方法

Mysql tinyint长度为1时在java中被转化成boolean型

查看>>

【刷题】BZOJ 3930 [CQOI2015]选数

查看>>

SQL分页排序的实现与分页数据重复问题——以Oracle rownum为例

查看>>

nagios 自定义插件demo

查看>>

Azure 基础 : 使用 Automation 定时开机

查看>>

使用Vim normal 命令修改可视块区域

查看>>

详细分享UICollectionView的自定义布局(瀑布流, 线性, 圆形...)

查看>>

visio的一些有用的方法

查看>>