正文

怎样学习哲学

author  author  2022-09-20  444

关键词：

怎样学习哲学

时间限制: 1 Sec 内存限制: 128 MB

题目描述

OI大师抖儿在夺得银牌之后，顺利保送pku。这一天，抖儿问长者：“虽然我已经保送了，但是我还要参加学考。马上就要考政治了，请问应该怎样学习哲学，通过政治考试？”
长者回答：“你啊，Too Young Too Simple,Sometimes Naive!哲学这种东西，不是说想懂就能懂的，需要静心撕烤。你去后面的森林里好好想想。”

长者的后院有一片哲♂学森林。由于一些奥妙重重的原因，这片森林构成了一个n*m的矩形，其中每个点就代表了一棵树。此外，由于辣鸡出题人KJDH从中捣鬼，有些树被连根拔起（也就是消失了）。抖儿每天都要到树下撕烤，因此他想要在每一行选择一棵树。但是他非常讨厌走回头路，因此第i行选择的树必须比第i-1行的靠右。现在抖儿想知道，总共有多少种选择的方案。

输入

第一行三个整数n,m,p，分别表示森林的长、宽，以及消失的树的数目。

接下来p行每行两个整数，表示第ai行第bi列的树消失了。

输出

一行一个整数，表示方案数。由于答案可能很大，请对1000003取模。

样例输入

3 5 2 2 3 3 4

样例输出

提示

【样例说明】

方案一：选（1,1）（2,2）（3,3）

方案二：选（1,1）（2,2）（3,5）

方案三：选（1,1）（2,4）（3,5）

方案四：选（1,2）（2,4）（3,5）

方案五：选（1,3）（2,4）（3,5）

【限制与约定】

测试点编号	n,m	p
1	n,m≤10
2
3
4
5	n,m≤100
6
7
8
9	n,m≤5000
10
11	n,m≤100000 n,m≤100000	p=0
12
13
14
15	n,m≤109	p=0
16
17
18
19
20

对于所有的数据，保证n,m≤109，p≤min(n*m,2000)

【后记】

在经历了长久的撕烤之后，抖儿终于领悟了哲♂学奥义。

抖儿对长者说：“我知道了！哲学源于生活，只有撕烤生活，才能领悟哲理。”

长者嘿嘿一笑：“你想多了。因为你在哲♂学之森中待的时间太长，政治学考已经在一个月前结束了。”

题解：话说我也是逃了政治课上来的。

这题50分直接动规。

先考虑p=0的情况，C(n,m)对吧。

那p!=0时我们只要减去不行的就可以了。

不行的怎么求不会重复那？我们只要在一条不合法的方案在第一个不合法的点减掉就可以了。

令dp[i]表示到达i且仅经过i这个空点方案总数。那么dp[i]=起始点到i的方案数-dp[j]*j到i的方案数。其中j是所有在i左上方的空点。

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
35 if(last==‘-‘)ans=-ans; return ans;
36 }
37 const int p=1000003;
38 struct node{
39     int a,b;
40 }f[3000];
41 bool cmp(node a,node b){
42     return (a.a<b.a)||(a.a==b.a && a.b<b.b);
43 }
44 ll dp[3000],fac[p],inv[p];
45 ll C(ll x,ll y){
46     if (y>x) return 0;
47     if (x<p && y<p)   return fac[x]*inv[y]%p*inv[x-y]%p;
48     return C(x/p,y/p)*C(x%p,y%p)%p;
49 }
50 int main(){
51     int n=read(),m=read(),k=read();
52     for (int i=1;i<=k;i++) f[i].a=read(),f[i].b=read();
53     int i;
54     for (fac[0]=1,i=1;i<p;i++) fac[i]=fac[i-1]*i%p;
55     for (inv[1]=1,i=2;i<p;i++) inv[i]=(p-p/i)*inv[p%i]%p;
56     for (inv[0]=1,i=1;i<p;i++) inv[i]=inv[i-1]*inv[i]%p;
57     ll sum=C(m,n);
58     k++; f[k].a=n+1; f[k].b=m+1;
59     sort(f+1,f+k+1,cmp);
60     for (int i=1;i<=k;i++){
61         dp[i]=C(f[i].b-1,f[i].a-1);
62         for (int j=1;j<i;j++)
63         if (f[i].b>f[j].b && f[i].a>f[j].a)
64             dp[i]=((dp[i]-dp[j]*C(f[i].b-f[j].b-1,f[i].a-f[j].a-1)%p)%p+p)%p;
65         sum=((sum-dp[i]*C(m-f[i].b,n-f[i].a)%p)%p+p)%p;
66     }   
67     printf("%lld",sum);
68     return 0;
69 }

View Code

线程学习五：哲学家就餐问题

问题描述：设有5个哲学家，共享一张放有5把椅子的桌子，每人分得一把椅子，但是，桌子上共有5只筷子，在每人两边各放一只，哲学家们在肚子饥饿时才试图分两次从两边拿起筷子就餐。条件：1）拿到两只筷子时哲学家才开... 查看详情

中国哲学简史学习笔记

1、哲学的任务是什么？我在第一章曾提出，按照中国哲学的传统，它的任务不是增加关于实际的积极的知识，而是提高人的精神境界。2、《世说》有一则说：“王子猷居山阴，夜大雪，眠觉，开室，命酌酒。四望皎然，因... 查看详情

机器学习的哲学思想

...作么，泪奔。再次摘抄下来，方便以后再读不仅仅是机器学习，大部分理工科的思想都可以从文史学科的角度去理解。正所谓大道至简，很多道理是共通的**。本文的内容是从哲学角度看待机器学习。文查看详情

我们如何学习3：人生哲学

我们如何学习3：人生哲学富贵不还乡，如锦衣夜行金钱的哲学战车之喻知行合一：系统与定投人生的几个重大选择时间管理的大一统理论蚁群算法我在学习总结的时候认识了一个人，我认识到，个人的金钱... 查看详情

程序员修炼之道学习记录之注重实效的哲学

我的源码让猫吃了软件的熵(无序)石头汤和煮青蛙你的知识财产交流查看详情

郑捷《机器学习算法原理与编程实践》学习笔记（第七章预测技术与哲学）7.3岭回归

7.3岭回归7.3.1验证多重共线性7.3.2岭回归理论7.3.3岭际分析7.3.4k值的判断7.3.5辅助函数（1）导入多维数据集：加载数据集defloadDataSet(filename):numFeat=len(open(filename).readline().split(‘ ‘))-1#getnumberoffieldsdataMat=[]labelMat=[]fr=ope 查看详情

郑捷《机器学习算法原理与编程实践》学习笔记（第七章预测技术与哲学）7.1线性系统的预测

7.1.1回归与现代预测 7.1.2最小二乘法 7.1.3代码实现（1）导入数据defloadDataSet(self,filename):#加载数据集X=[];Y=[]fr=open(filename)forlineinfr.readlines():curLine=line.strip().split(‘ ‘)X.append(float(curLine[0]) 查看详情

spark与scikit-learn机器学习流程组件设计哲学比较

...建的一组统一的高级API，帮助用户创建和调整实用的机器学习流程。有关子包的指南，请参阅下面的算法指南部分spark.ml，包括PipelinesAPI特有的功能转换器，集合等。管道中的主要概念SparkML标准化了用于机器学习算法的API，使得... 查看详情

华电非全研究生学习和工作总结(2021.11.15-2021.11.28)-哲学

上周和本周总结合为一篇，因为上周实在是没学什么东西，有点忙，有点浮躁。。。哎呀，我们软件工程老师估计是个杰伦迷(其实我也是)，开课前连放几首周杰伦的歌曲，听得让人陶醉，同学们误以为进错了频道，哈哈。截图... 查看详情

华电非全研究生学习和工作总结(2021.11.15-2021.11.28)-哲学

《机器学习理论方法及应用》研读

...环境、实现自我完善等。机器学习：机器学习是一门研究怎样用计算机来模拟或实现人类学习活动的学科，是计算机科学、数学、心理学、生物学和哲学等多门学科的查看详情

算法卢卡斯定理

...了，但是我还要参加学考。马上就要考政治了，请问应该怎样学习哲学，通过政治考试？”长者回答：“你啊，TooYoungTooSimple,SometimesNaive!哲学这种东西，不是说想懂就能懂的，需要静心撕烤。你去后面的森林里好好想想。”长者... 查看详情

Go 中的哲学家就餐问题未通过单元测试

...ittest【发布时间】：2022-01-1719:09:58【问题描述】：我正在学习围棋课程，其作业如下：用下面的方法实现餐饮哲学家的问题约束/修改。应该有5个哲学家共用筷子，每对相邻的哲学家之间有一根筷子。每个哲学家应该只吃3次（而... 查看详情

哲学专业学啥课程

参考技术A一、哲学学什么哲学专业主要学习课程有哲学概论、马克思主义哲学原理、中国哲学史、西方哲学史、科学技术哲学、伦理学、宗教学、美学、逻辑学、心理学、中外哲学原著导读等。二、哲学定义哲学关于世界观和... 查看详情

政治-徐涛01.马原

...　　　唯物论（世界是什么）　　　　辩证法（世界是怎样的）　　　　认识论（如何认识外部世界的问题）　　　　唯物史观（人是什么社会是什么）　　1.哲学基本问题的两个方面　　　　物质和意识何者为第一性　... 查看详情

我们如何学习3：人生哲学

我们如何学习3：人生哲学富贵不还乡，如锦衣夜行金钱的哲学战车之喻知行合一：系统与定投人生的几个重大选择时间管理的大一统理论蚁群算法人生没有成功，只有成长我在学习总结的时候认识了一个人，... 查看详情

开源软件：信息共赢的哲学

...想，开源这回事，不就是大家把代码传到网上，给人下载学习，之后有了Linux，Apache一系列牛逼作品么？这么简单接地气的事情，为什么要搞得那么形而上呢？开源也给我带来了不少的困惑，很多商业软件的授权费... 查看详情