题目描述 这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！ 输入格式 一行包含两个整数N，M，之间由一个空格隔开。 输出格式 总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。 输入输出样例 输入 #1 1 3 输出 #1 7 说明/提示 样例说明 除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有222-1...

Description Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。 Input 一个整数，为N。 Output 一个整数，为所求的答案。 Sample Input 6 Sample Output 15 HINT 0<N<=2^32。 分析 考虑枚举     d   =   g   c   d   (   i   ,   n   )    d = gcd(i,n)   d=gcd(i,n) 于是有    <munderover>  ∑    i   =  ...

Description 大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。 Input 第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n Output 共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值 Samp...

Description 给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能 被2整除，其中末位为2的有30种，末位为4的有60种。 Input 输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1 , 2, 3, 4, 5, 6, 7, 8, 9. Output 每个数据仅一行，表示能被d整除的排列的个数。 Sample Input 7 000 1 001 1 1234567890 1 123434 2 1234 7 12345 17 12345678 29 Sample Outpu...

描述 八是个很有趣的数字啊。八=发，八八=爸爸，88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样，有趣吧。当然题目和这些都没有关系。 某个人很无聊，他想找出[a,b]中能被8整除却不能被其他一些数整除的数。 格式 输入格式 第一行一个数n，代表不能被整除的数的个数。 第二行n个数，中间用空格隔开。 第三行两个数a，b，中间一个空格。 输出格式 一个整数，为[a,b]间能被8整除却不能被那n个数整除的数的个数。 样例1 样例输入1 3 7764 6082 462 2166 53442 样例输出1 6378 限制 各个测试点1s 提示 对于30%的数据， 1≤n≤5，1≤a≤b≤100...

分析 在变化的量是啥？已经打的点的集合，还有当前生成树的深度。 于是我们用      f   [   s   ]   [   i   ]    f[s][i]   f[s][i] 表示已打的集合为      s    s   s ， 生成树深度为      i    i   i 的最小代价。 转移的话，答案肯定是由      S    S   S 的子集转移而来，我们就枚举子集，剩下的点作为第      i    i   i 层，以此得到转移方程：      f   [   S   ]   [   i   ]   =   m   i   n   (   f   [   S   0   ]   ...

Description  Input 输入包含一行两个整数N和K，1<=N,K<=10^9 Output 一行一个整数，表示不同方案数目模1,000,000,007的值。 Sample Input 2 2 Sample Output 16 我好菜啊。。。看      w   i   l   l    will   will 老师讲解，我的思维过程：我先看看自己能不能想出来把，算了算了听讲，woc牛逼！暂停一会接下来的我应该可以自己想出来了，算了算了再听一会，woc牛逼！得出结论：我是真的菜。。。 分析 这题真是一道思维题啊！首先看数据范围，数据范围这么大，应该是道结论题。 我们先用...

Description JYY 带队参加了若干场ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。 JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？当然，JYY 不希望任 何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。 例如，JYY 带来了2 袋麻花和1 袋包子，分给A 和B 两位同学，那么共有4 种不同的 分配方法： A：麻花，B：麻花、包子 A：麻花、麻花，B：包子 A：包子，B：麻花、麻花 A：麻花、包子，B：麻花 Input 输入数据第一行是同学的数量N 和特产的数量M。 第二行包含M 个整数，表示每一种特产的数量。 N, M...

Description 棋盘是一个n×m的矩形，分成n行m列共n*m个小方格。 现在萌萌和南南有C种不同颜色的颜料，他们希望把棋盘用这些颜料染色，并满足以下规定： 1.棋盘的每一个小方格既可以染色（染成C种颜色中的一种），也可以不染色。 2.棋盘的每一行至少有一个小方格被染色。 3.棋盘的每一列至少有一个小方格被染色。 4.种颜色都在棋盘上出现至少一次。 以下是一些将3×3棋盘染成C=3种颜色（红、黄、蓝）的例子：  请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同， 即认为两个染色方案是不同的 Input 输入只有一行 3 个整数n,m,c。1 < = n,m,c &l...

Description 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s i的价值的东西。请问每次有多少种付款方法。 Input 第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000 Output 每次的方法数 Sample Input 1 2 5 10 2 3 2 3 1 10 1000 2 2 2 900 Sample Output 4 27 分析 嘿嘿嘿容斥终于学有用了。 这题本质上求满足方程       x   1     c  ...

Problem Description Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)…… 这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果...

前置知识 狄利克雷卷积 形如      f   (   n   )   =  <munder>  ∑    d   ∣   n   </munder>  g   (   d   )   ∗   h   (  <mstyle displaystyle="true" scriptlevel="0">   n   d   </mstyle>  )    f(n) = \sum\limits_{d|n} g(d)*h(\dfrac{n}{d})   f(n)=d∣n∑​g(d)∗h(dn​)，记作      f  ...

Description A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling sche...

题目描述 设d(x)为x的约数个数，给定N、M，求       ∑    i   =   1    n     ∑    j   =   1    m    d   (   i   j   )    \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij)   i=1∑n​j=1∑m​d(ij) 输入格式 输入文件包含多组测试数据。第一行，一个整数T，表示测试数据的组数。接下来的T行，每行两个整数N、M。 输出格式 T行，每行一个整数，表示你所求的答案。 输入输出样例 输入 #1 2 7 4 5 6 输出 #1 110 121 说明/提示 1<=N,...