容斥原理 – Tgotp-Blog

#185. 【ZJOI2016】小星星

考虑的f[i][j]表示第i个点映射到图中第j个点上(可重)得方案数

树形dp,然后容斥搞一搞就好了。

c++代码如下:

 

1853: [Scoi2010]幸运数字

发现和上一题很像(基本差不多),但是做了以后觉得上一次过纯属侥幸,完全没有考虑到乘法的时间问题,应该倒序相乘来减小得到的sum值。

容斥原理。

c++代码如下:

 

2393: Cirno的完美算数教室

容斥裸题。

直接求出1 – r内的baka数,然后套容斥就搞定了。

c++代码如下:

 

1042: [HAOI2008]硬币购物

dp + 容斥原理。

首先dp算出不计硬币的所有钱数的方案数,然后分别计算出每一种超的情况,利用容斥原理解决问题,容斥的一块可以dfs可以用状压。

c++代码如下:

 

T9760 2017

题目背景

四川省ACM 2017 G题

题目大意:

给定四个整数a,b,c,d,a <= x <= b,c <= y <= d

求出有多少对x,y使得x*y是2017的倍数。

题目描述

Given a, b, c, d, find out t[……]

Read more