数论一,递推DP

1、UVa 10916  Factstone
Benchmark(对数函数的运–乘化加)

A –
数字三角形

题解:
一旦get马克斯(i,j)表示点(i,j)到底层的最为丰盛路,
那么getMax(i,j)=max(getMax(i+1,j),getMax(i+1,j+1))+triangle[i][j];
用maxSum[i][j]存取中间结果;

  题意:给有东,每个10年针对承诺一个时电脑可支撑之字节位数,总结n!
< max(max 为眼前统计机能表示的极其特别整数),求最好特别n.

  • 记念化搜索

  思路:字节数k = (year – 1940) / 10, 
问题就转账成 n ! < 2 ^ k < (n + 1) !,
对片度同取对数,因为log(a*b) = log(a) + log(b);所以log(n!) =
sum(log(i)), ( 1<= i <= n), 只要找到最好小的sum(log(i)) > k *
log(2) ,答案就是是i- 1.

lovebet爱博体育 1lovebet爱博体育 2

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=105;
int triangle[MAXN][MAXN];
int maxSum[MAXN][MAXN];
int n;
int getMax(int i,int j)
{
    if(i==n) return maxSum[i][j]=triangle[i][j];
    if(maxSum[i][j]!=-1) return maxSum[i][j];
    return maxSum[i][j]=max(getMax(i+1,j),getMax(i+1,j+1))+triangle[i][j];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&triangle[i][j]);
        }
    }
    memset(maxSum,-1,sizeof(maxSum));
    printf("%d\n",getMax(1,1));
}
 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 int main()
 5 {
 6     int y;
 7     while (~scanf("%d", &y)&&y)
 8     {
 9         int n = (y - 1940) / 10;
10         double re = pow(2.0,1.0*n)*log(2.0);
11         double sum = 0;
12         for(int i=1;;i++)
13         {
14             sum += log(1.0*i);
15             if (sum > re)
16             {
17                 printf("%d\n", i - 1);
18                 break;
19             }
20         }
21     }
22     return 0;
23 }
  • 嵌套循环

View Code

2、zoj 1239 Hanoi Tower Troubles
Again!

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=105;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&triangle[i][j]);
        }
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res=max(res,dp[n][i]);
    }
    printf("%d\n",res);
}

  题意:给出n个支柱,从第一单支柱起头拓宽珠子,珠子编号从1方始,要求每个柱子上相邻两独珠子的跟是平方数。

母牛的故事
题意:
爆发同条母牛,它每年年底丰硕一匹微微母牛。每头小母牛从第多只新春先导,每年年终为老一峰小母牛。请编程实现以第n年的时,共有多少头母牛?
题解:
如第n年母牛的数目为f(n),则第n年之牛的数码相当于原来的初的母牛数量增长新出生之牛数量,旧的母牛数量等于f(n-1),因为小母牛从第四年开才初非常一匹母牛,也虽然是三年前的母牛才发出特别多少母牛的能力,所以新发生的母牛的数额相等三年前之牛的多少

  思路:

  • 记忆化搜索:

h(1) =
1:1只支柱时,放上1从此,2虽推广不上了,不满足柱子上附近的球之和也平方数(1

  • 2 = 3,不是平方数);
    h(2) =
    3:2只支柱时,1跟2各类在1独支柱上,3得置身1下边(1 + 3 = 4 = 2 ^
    2);
    h(i) = h(i – 1) + i + 1:i为奇数时,在i –
    1柱子的根底及扩大了一个柱,这时候可以重复推广i + 1只圆球;
    h(i) = h(i – 1) + i:i为偶数时,在i –
    1柱子的底蕴及添了一个支柱,那时候能够更松开i个球。
    f(n) = f(n – 1) + (n + 1) / 2 + (n + 1)
    / 2 (n > 2)
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=60;
int sum[60];
int f(int n)
{
    if(sum[n]!=-1) return sum[n];
    if(n<5) return sum[n]=n;
    return sum[n]=f(n-1)+f(n-3);
}
int main()
{
    memset(sum,-1,sizeof(sum));
    int n;
    while(scanf("%d",&n)!=EOF,n)
    {
        printf("%d\n",f(n));
    }
}

lovebet爱博体育 3lovebet爱博体育 4

  • lovebet爱博体育,嵌套循环:
 1 //h(1) = 1:1个柱子时,放上1之后,2就放不上去了,不满足柱子上相邻的球之和为平方数(1 + 2 = 3,不是平方数);
 2 //h(2) = 3:2个柱子时,1和2各放在1个柱子上,3可以放在1上面(1 + 3 = 4 = 2 ^ 2);
 3 //h(i) = h(i - 1) + i + 1:i为奇数时,在i - 1柱子的基础上增加了一个柱子,这时候可以再放i + 1个球;
 4 //h(i) = h(i - 1) + i:i为偶数时,在i - 1柱子的基础上增加了一个柱子,这时候可以再放i个球。
 5 // f(n) = f(n - 1) + (n + 1) / 2 + (n + 1) / 2    (n > 2)
 6 #include<iostream>
 7 using namespace std;
 8 int re[55];
 9 void Init()
10 {
11     re[1] = 1, re[2] = 3;
12     for (int i = 3; i <= 50; i++) re[i] = re[i - 1] + (i + 1) / 2 + (i + 1) / 2;
13 }
14 int main()
15 {
16     Init();
17     int t;
18     scanf("%d", &t);
19     while (t--)
20     {
21         int n;
22         scanf("%d", &n);
23         printf("%d\n", re[n]);
24     }
25     return 0;
26 }

View Code

#include<cstdio>
using namespace std;
const int MAXN=60;
int dp[60];
int main()
{
    for(int i=1;i<=4;i++)
    {
        dp[i]=i;
    }
    for(int i=5;i<55;i++)
    {
        dp[i]=dp[i-1]+dp[i-3];
    }
    int n;
    while(scanf("%d",&n)!=EOF,n)
    {
        printf("%d\n",dp[n]);
    }
}

3、hdu1465 不容易系列之一(错排)

平面划分问题
讲明出处,摘自
http://www.cnblogs.com/chaosheng/archive/2012/01/26/2329583.html
(1) n条直线最多分割平面问题
题目大致如:n条直线,最多好将平面分为稍只区域。
分析:可能您先就是表现了就题目,这最多是相同鸣初中的思考题。但一个类的题目或者从简单的入手,才好察觉规律。当起n-1长直线时,平面最多让分为了f(n-1)个区域。则第n漫漫直线假诺切成的区域屡最好多,就必须同每条直线相交且不克有同一交点。这样就是会拿走n-1个交点。那一个交点将第n长达直线分为2条射线和n-2长长的线断。而诸条射线和线断将因为局部区域一分为二。这样虽差不多有了2+(n-2)个区域。
故:f(n)=f(n-1)+n=f(n-2)+(n-1)+n= ……=f(1)+1+2+……+n =n(n+1)/2+1
(2) 折线分割平面(hdu2050)
据悉直线分平面可知,由交点决定了射线和线的条数,进而决定了增产的区域屡。当n-1漫漫折线时,区域屡也f(n-1)。为了使多的区域最多,则折线的星星度的线条要同n-1长达折线的无尽,即2*(n-1)条线段相交。那么新增的线段数为4*(n-1),射线数为2。但若是注意的凡,折线自相邻之点滴线段只可以加一个区域。
故f(n)=f(n-1)+4(n-1)+2-1
=f(n-1)+4(n-1)+1
=f(n-2)+4(n-2)+4(n-1)+2
……
=f(1)+4+4*2+……+4(n-1)+(n-1)
=2n^2-n+1
(3) 封闭曲线分平面问题
题目大致如存在n条封闭曲线画在面上,而此外两修封闭曲线恰好相交于片点,且任何三久封闭曲线不交于同一些,问这些封闭曲线拿平面分割成的区域个数。
解析:当n-1个圆时,区域屡为f(n-1).那么第n只完美就务须跟眼前n-1单圆相交,则第n单周被分为2(n-1)段线段,扩展了2(n-1)个区域。
故: f(n)=f(n-1)+2(n-1)=f(1)+2+4+……+2(n-1) =n^2-n+2
(4)平面分割空间问题(hdu1290)
鉴于二维的分问题能,平面分割和线内的交点有关,即交点决定射线和线条的条数,从而决定新增的区域屡。试想在三维中即便是否和平面的交线有关吗?当起n-1只面时,分割的空间数为f(n-1)。要起尽多之空间数,则第n个面需和前n-1单面相交,且非克起联手的交线。即绝多起n-1
长交线。而立n-1长交线把第n单面最多分割成g(n-1)个区域。(g(n)也(1)中的直线分平面的个数)此平面将故的长空一分为二,则太多扩大g(n-1)个空中。
故:f(n)=f(n-1)+g(n-1) ps:g(n)=n(n+1)/2+1
=f(n-2)+g(n-2)+g(n-1)
……
=f(1)+g(1)+g(2)+……+g(n-1)
=2+(1*2+2*3+3*4+……+(n-1)n)/2+(n-1)
=(1+22+32+42+……+n2-1-2-3-……-n )/2+n+1
=(n^3+5n)/6+1
折线分割平面
题解:

  题意:求所起错排的错排方案往往。

#include<cstdio>
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",2*n*n-n+1);
    }
}

  思路:

面分割球体
题解:

错排数公式:f[n] = (n – 1) * (f[n –
1] + f[n – 2]);
否可如此想;
(1).f[1] = 0; f[2] = 1;
(2).即便确定f[n – 1] 和 f[n – 2]
的话。
f[n] 中必蕴含 f[n – 1] * (n –
1)种情景。
即把新参预的相同查封与在此之前的任一一封互换,所获取的肯定是错排。

#include<cstdio>
int main()
{
    int n;
    while(~scanf("%d",&n))
    printf("%d\n",(n*n*n+5*n)/6+1);
}

lovebet爱博体育 5lovebet爱博体育 6

Working
out

题意:
有n*m个格子,
走过一个格子可以得相应的分数.一个人口由左上角出发走至右下角,只可以于左走或者为下移动;另一个丁起左下角出发走至右上较量,只好望左侧走或提升移动;中途两独人口只能有同三回于相见,相遇的方格的分数不到底进来,问三只人可以获取的极要命分数;
题解:

 1 //错排数公式:f[n] = (n - 1) * (f[n - 1] + f[n - 2]);
 2 //也可以这么想;
 3 //(1).f[1] = 0; f[2] = 1;
 4 //(2).如果确定f[n - 1] 和 f[n - 2] 的话。
 5 //f[n] 中必然包含 f[n - 1] * (n - 1)种情况。 即把新加入的一封和之前的任一一封交换,所得到的必然是错排。
 6 //f[n] 中另一部分就是f[n - 2] * (n - 1) 即之前的 n - 1 封中有一封没有错排,把这封与新加入的一封交换进行错排。
 7 #include<iostream>
 8 using namespace std;
 9 long long re[25];
10 void Init()
11 {
12     re[1] = 0, re[2] = 1;
13     for (int i = 3; i <= 20; i++) re[i] = (re[i - 1] + re[i - 2])*(i - 1);
14 }
15 int main()
16 {
17     Init();
18     int n;
19     while (~scanf("%d", &n))
20     {
21         printf("%lld\n",re[n]);
22     }
23     return 0;
24 }
  • 因为少单人口只好相遇一破,所以遭逢点未可知当一侧
  • 如若A为下一致步到相遇点,那么B无法往达移动相同步到相遇点,为了只相遇一不行,A只可以再累往下走;同时,B向左边走,B继续为右边走;
  • 同理,假若A向左侧一步走及相遇点,A继续朝右边走;B向上走相同步到相遇点,B继续往左边走;
  • 季单方向的dp
    dp1[i][j] := 从 (1, 1) 到 (i, j) 的极端要命分数
    dp2[i][j] := 从 (i, j) 到 (n, m) 的不过深分数
    dp3[i][j] := 从 (n, 1) 到 (i, j) 的最好充足分数
    dp4[i][j] := 从 (i, j) 到 (1, m) 的最老分数
    即便如此分的极酷价值对许者的一定量种情景

View Code

4、HDU 3625 Examining the
Rooms(第一好像斯特林数)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int dp1[MAXN][MAXN];
int dp2[MAXN][MAXN];
int dp3[MAXN][MAXN];
int dp4[MAXN][MAXN];
int graph[MAXN][MAXN];
int n,m;
void init()
{
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    memset(dp3,0,sizeof(dp3));
    memset(dp4,0,sizeof(dp4));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp1[i][j]=max(dp1[i][j-1],dp1[i-1][j])+graph[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            dp2[i][j]=max(dp2[i][j+1],dp2[i+1][j])+graph[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            dp3[i][j]=max(dp3[i][j+1],dp3[i-1][j])+graph[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            dp4[i][j]=max(dp4[i][j-1],dp4[i+1][j])+graph[i][j];
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&graph[i][j]);
        }
    }
    init();
    int ans=0;
    for(int i=2;i<n;i++)
    {
        for(int j=2;j<m;j++)
        {
            ans=max(ans,dp1[i-1][j]+dp2[i+1][j]+dp3[i][j+1]+dp4[i][j-1]);
            ans=max(ans,dp1[i][j-1]+dp2[i][j+1]+dp3[i-1][j]+dp4[i+1][j]);
        }
    }
    printf("%d\n",ans);
}

  题意:有n个房间,n!个钥匙,在屋子中,最多可排除k扇门,然后拿走里的钥匙,去开任何的山头,不过首先扇门未得以破开,求好打开所有门的票房价值。

排计数

  思路:

排计数的第一维一般是1~i的排列的方案往往,第二维第三维依据条件来定义

Attack on
Titans

题意:
有R,G,B三栽士兵,一共来n个;求至少有m个连续G士兵,最多来k个连续R士兵的排列的种数。
题解:
预先管题目都转发成至多连续的情事:
至少m个连续G,至多k个连续R
=至多n个连续G,至多k个连续连接R 减去 至多k个连续R,至多(m-1)个连续G
dp[i][j] 至多有u个连续G,至多有v个连续R的个数,u,v为常数
dp[i][0]意味着第i独岗位放G且到多起u个连G,至多有v个连续R
dp[i][1]意味着第i独岗位放R且到多暴发u个连G,至多生v个连续R
dp[i][2]表示第i只地方放P且到多来u独连续G,至多出v个连续R

  • 当第i只为P,前一个怎么推广都足以
    dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
  • 当第i个为G时
  • 设i<=u 时 无论前一个庸放都非会合超越u个连的G士兵
  • dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
  • 使i=u+1时时,要排除前u个还加大了G的情景
  • dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1;
  • 当 i > u + 1平常,我们最好操心之是啊?第i – 1 到 i –
    u都是G士兵,那么此时以i号地方放置G士兵,也以不抱约束
    俺们可减去非吻合约束之方案往往,当 i – 1 到 i – u都是G士兵时
    有小种方案?肯定当地方i – u -1是R或者P啦
  • dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1000010;
const LL MOD=1000000007;
LL dp[MAXN][3];
int n,m,k;
LL work(int u,int v)
{
    dp[0][0]=dp[0][1]=0;
    dp[0][2]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;

        if(i<=u) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;
        else if(i==u+1) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1+MOD)%MOD;
        else if(i>u+1) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]+MOD)%MOD;

        if(i<=v) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2])%MOD;
        else if(i==v+1) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2]-1+MOD)%MOD;
        else if(i>v+1) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2]-dp[i-v-1][0]-dp[i-v-1][2]+MOD)%MOD;
    }
    return (dp[n][0]+dp[n][1]+dp[n][2])%MOD;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    printf("%lld\n",((work(n,k)-work(m-1,k))%MOD+MOD)%MOD);
    return 0;
}

Coin
Toss

题意;
长度为n的字符串仅出于H和T组成,求出最少包括k个连续的H的尺寸为n字符串的总和
题解:
以及齐;因为求出总数较特别,所以用java大数

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    private static BigInteger dp[][]=new BigInteger[110][2];
    private static BigInteger work(int n,int k)
    {
        dp[0][0]=new BigInteger("0");
        dp[0][1]=new BigInteger("1");
        for(int i=1;i<=n;i++)
        {
            dp[i][1]=dp[i-1][1].add(dp[i-1][0]);
            if(i<=k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]);
            else if(i+1==k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]).subtract(BigInteger.ONE);
            else if(i>k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]).subtract(dp[i-k-1][1]);
        }
        return dp[n][0].add(dp[n][1]);
    }
    public static void main(String[] args) {
        int n,k;
        Scanner in=new Scanner(System.in);
        while(in.hasNextInt())
        {
            n=in.nextInt();
            k=in.nextInt();
            System.out.println(work(n,n).subtract(work(n,k-1)));
        }
    } 
}

Mex
霸占坑占坑
占用坑占坑
占据坑占坑
霸占坑占坑
The King’s Ups and
Downs

题意:
暴发n个身高不相同的新兵,求出身高呈现波浪状(高低高如故高低)的排列数
题解:
要是前面n-1个人都破好,那么对第n私有来讲,他自然是最高的,所以他插入到武装部队被,前面这段的结尾一定是出于大及低位,前面这段的启幕一定是不及到强;假若了解前边结尾高低之主意数n和后起始没有高的法门数m。那么在拖欠职务的章程数就为n*m;假设dp[i][0]表示有i个人还最终是高低之计数,dp[i][1]表示有i个人还先导是底高的不二法门数,我们枚举前面的长短j
[0,i-1],那么方法数ans[i]+=dp[j][0]*dp[i-j-1][1]*C[i-1][j];c[i-1][j]否组合数,因为起i-1个数字选出j个放置前面;由于镜像的干,dp[i][0]=dp[i][1]=ans[i]/2;

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=25;
long long dp[25][2];
long long cal[25][25];
long long ans[25];
int main()
{
   for(int i=0;i<21;i++)
   {
       cal[i][0]=1;
       for(int j=1;j<i;j++)
       {
           cal[i][j]=cal[i-1][j]+cal[i-1][j-1];
       }
       cal[i][i]=1;
   }
   dp[0][0]=1;
   dp[0][1]=1;
   dp[1][0]=1;
   dp[1][1]=1;
   memset(ans,0,sizeof(ans));
   ans[1]=1;
   for(int i=2;i<21;i++)
   {
       for(int j=0;j<i;j++)//枚举前面的长度
       {
           ans[i]+=dp[j][0]*dp[i-j-1][1]*cal[i-1][j];
       }
       dp[i][0]=dp[i][1]=ans[i]/2;
   }
   int t;
   scanf("%d",&t);
   int cas,n;
   while(t--)
   {
       scanf("%d%d",&cas,&n);
       printf("%d %lld\n",cas,ans[n]);
   }
    return 0;
}

Number
String

题意:
输入一错由’I’,’D’,’?’组成的长为n的字符串;’I’表示前一个数字与如今数字是升序关系,’D’表示前一个数字和眼前数字是降序关系,’?’表示任意顺序;比如排
{3, 1, 2, 7, 4, 6, 5} 表示也字符串 DIIDID。
统计有所可以生为定字符串的班数量,每个阵含n+1单数字,分别吗1~n+1,即于1最先都非还。
题解:
因为dp[i]的第一维是1-i的排列的方案,为了反映大小关系,第二维应为数值;
假设dp[i][j]表示前i个满意字符串条件的最后为j的 i
的排,注意是i的排列,前边并没有数大于i;
如果s[i – 1]是’ I ‘,那么dp[i][j] = dp[i-1][j-1] +
dp[i-1][j-2] + .. + dp[i-1][1]
然更简化,dp[i][j] = dp[i][j-1]+dp[i-1][j-1]
如果s[i – 1]是‘D’,那么dp[i][j] = dp[i-1][j] +
dp[i-1][j+1] + … + dp[i-1][i-1]
但更简化,dp[i][j] = dp[i-1][j+1]+dp[i-1][j]
盖只要使得时各吗j,假诺前现身过j,就令后面的富有大于等于j的数+1,就可知协会出新的排了。比如
{1, 3, 5, 2, 4},要以第六号插入3,令 >=
3的数都+1,于是便布局出新的排列{1, 4, 6, 2, 5, 3}。

#include<cstdio>
#include<cstring>
using namespace std;
const int MOD=1000000007;
const int MAXN=1010;
char str[MAXN];
int dp[MAXN][MAXN];
int main()
{
    while(scanf("%s",str+1)!=EOF)
    {
        int len=strlen(str+1);
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;
        for(int i=2;i<=len+1;i++)
        {
            if(str[i-1]=='I')
            {
                for(int j=2;j<=i;j++)
                {
                    dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%MOD;
                }
            }
            else if(str[i-1]=='D')
            {
                for(int j=i-1;j>=1;j--)
                {
                    dp[i][j]=(dp[i][j+1]+dp[i-1][j])%MOD;
                }
            }
            else
            {
                int sum=0;
                for(int j=1;j<=i-1;j++)
                {
                    sum=(sum+dp[i-1][j])%MOD;
                }
                for(int j=1;j<=i;j++)
                {
                    dp[i][j]=sum;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=len+1;i++)
        {
            ans=(ans+dp[len+1][i])%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

求N个房间形成1~K独环有多少种或,然后除以总的分配方案往往就为题材要大家呼吁之票房价值。

第一像样斯特林数S(N, K) = S(N – 1, K – 1) +
(N – 1)*S(N – 1,
k)恰恰就是是求N个要素形成K个非空循环排列的模式数。

S(N,M)-S(N-1,M-1),表示N个元素形成M个环,减去1独成环,即剩下的N-1单要素形成M-1单绕,算得之结果就是是所求值。

lovebet爱博体育 7lovebet爱博体育 8

 1 //求N个房间形成1~K个环有多少种可能,然后除以总的分配方案数即为题目要我们求的概率
 2 //第一类斯特林数S(N, K) = S(N - 1, K - 1) + (N - 1)*S(N - 1, k)恰恰就是求N个元素形成K个非空循环排列的方法数
 3 //S(N,M)-S(N-1,M-1),表示N个元素形成M个环,减去1独自成环,即剩下的N-1个元素形成M-1个环,算得的结果便是所求值
 4 #include<iostream>
 5 using namespace std;
 6 long long stl[25][25], cal[25];
 7 void Init()
 8 {
 9     cal[0] = cal[1] = 1;
10     for (int i = 2; i <= 20; i++) cal[i] = cal[i - 1] * i;
11     for (int i = 1; i <= 20; i++)
12     {
13         stl[i][i] = 1;
14         for (int j = 1; j < i; j++)
15         {
16             stl[i][j] = stl[i - 1][j - 1] + (i - 1)*stl[i - 1][j];
17         }
18     }
19 }
20 int main()
21 {
22     int t;
23     scanf("%d", &t);
24     Init();
25     while (t--)
26     {
27         int n, k;
28         scanf("%d%d", &n, &k);
29         long long ans = 0;
30         for (int i = 1; i <= k; i++)
31         {
32             ans += stl[n][i] - stl[n - 1][i - 1];
33         }
34         printf("%.4lf\n", 1.0*ans / cal[n]);
35     }
36     return 0;
37 }

View Code

5、hdu 4045 Machine
scheduling(组合+第二类斯特林数)

  题意:有N个机器,每一日选出R个机器,而且各半单机器的数码差而超过等于K,而且天天将R个机器太多分为M组工作,问尽多有微微种方案

  思路:

第一是起N个机器中选出R个知足条件的机来微种。然后以R个机器太多分为M组有稍许种,答案吧双边的乘积。

对此后者:

也次好像Strling数的和 : S[n][1] +
S[n][2] + … + S[n][m]。

S(p,k)的递推公式是:S(p,k)=k*S(p-1,k)+S(p-1,k-1)
,1<= k<=p-1
边界条件:S(p,p)=1 ,p>=0 ;S(p,0)=0 ,p>=1。

对在此以前者:

1:假诺是管n个求放入k个盒子中(每个盒子必须使生球),那么由插板法得
方案往往也 C(n-1,k-1);
2:假诺是把n个求放入k个盒子中(盒子可为空),那么由插板法得
方案往往为 C(n + k – 1, k – 1);
一旦由n个元素编号1~n中选出r个要平昔,使得任意四个元素编号相差>=k
解法:先按照 1 k + 1 2 * k + 1 …. (r –
1)*k + 1 吗虽然是刚 间隔 k个排列下来
那么 总共n个元素,剩余 n – (r – 1)*k –
1单要素得以当作空格,极为space, 将她插入这r只因素的r +
1独空档中,
那样尽管可以保证枚举了向的艺命理术数,切满意任意两独要素编号相差
>= k的求
由此是问题简化为:将space个因素分配至r
+
1个区域被,可以为空(每半单机器在此之前至少有K个间隔,那么只要还剩下部分地方,则把这个剩余的插入到R个机器中。那么余下地点就是是N

  • ((R – 1)*K + 1), 对于R个机器,R + 1个职务,接下去就是是把N – ((R –
    1)*K + 1)分为R + 1单集,而且可以为空。做法是填补加R +
    1只物品,然后据此插板法,那样保证
    每一个聚都至少有一个,然后又将各级一个凑都减掉一个即是结果,最终结出就是是C[N
  • ((R – 1)*K + 1) + R + 1 – 1][R]。)

lovebet爱博体育 9lovebet爱博体育 10

 1 //有N个机器,每天选出R个机器,而且每两个机器的编号差要大于等于K,而且每天将R个机器最多分为M组工作,问最多有多少种方案 
 2 //1:如果是把n个求放入k个盒子中(每个盒子必须要有球),那么由插板法得 方案数为 C(n-1,k-1);
 3 //2:如果是把n个求放入k个盒子中(盒子可以为空),那么由插板法得 方案数为 C(n + k - 1, k - 1);
 4 //要从n个元素编号1~n中选出r个元素来,使得任意两个元素编号相差>=k
 5 //解法:先按照 1 k + 1 2 * k + 1 .... (r - 1)*k + 1 也就是刚好 间隔 k个排列下来
 6 //那么 总共n个元素,剩余 n - (r - 1)*k - 1个元素可以看成空格,极为space, 将它们插入这r个元素的r + 1个空档中,
 7 //这样就能保证枚举了素有的方法数,切满足任意两个元素编号相差 >= k的要求
 8 //所以这个问题简化为:将space个元素分配到r + 1个区域中,可以为空(每两个机器之前至少有K个间隔,那么如果还剩余一些位置,则把这些多余的插入到R个机器中。那么剩余位置便是N - ((R - 1)*K + 1), 对于R个机器,R + 1个位置,接下来便是把N - ((R - 1)*K + 1)分为R + 1个集合,而且可以为空。做法是添加R + 1个物品,然后用插板法,这样保证 每一个集合都至少有一个,然后再把每一个集合都减掉一个便是结果,最终结果便是C[N - ((R - 1)*K + 1) + R + 1 - 1][R]。)
 9 #include<iostream>
10 using namespace std;
11 const int maxn = 1010;
12 const int MOD = 1e9 + 7;
13 long long C[maxn][maxn];
14 long long stri2[maxn][maxn];//第二类斯特林数
15 void Init()
16 {
17     memset(C, 0, sizeof(C));
18     for (int i = 0; i < maxn; i++)
19     {
20         C[i][0] = 1;
21         for (int j = 1; j <= i; j++)
22         {
23             C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
24         }
25     }
26     for (int i = 1; i < maxn; i++)
27     {
28         stri2[i][0] = 0;
29         stri2[i][i]=stri2[i][1] = 1;
30         for (int j = 1; j < i; j++)
31         {
32             stri2[i][j] = (stri2[i - 1][j] * j + stri2[i - 1][j - 1]) % MOD;
33         }
34     }
35 }
36 int main()
37 {
38     Init();
39     int n, r, k, m;
40     while (~scanf("%d%d%d%d", &n, &r, &k, &m))
41     {
42         int res = n - (r - 1)*k - 1;
43         if (res < 0)
44         {
45             printf("0\n");
46             continue;
47         }
48         long long ans = 0;
49         for (int i = 0; i <= m; i++) ans = (ans + stri2[r][i]) % MOD;
50         ans = (ans*C[res + r][r]) % MOD;
51         printf("%lld\n", ans);
52     }
53     return 0;
54 }

View Code

6、HDU 1023 Train Problem
II(Carter兰数+模拟大数乘除<高精度递推>)

  题意:给你一个数n,表示来n辆火车,编号从1届n,从天驶过来,问你生小种出站的也许。

  思路:

1.Catalan数底整合公式为 Cn=C(2n,n) /
(n+1);
2.此数底递归公式为 h(n ) = h(n-1)*(4*n-2) / (n+1)。

http://blog.163.com/lz\_666888/blog/static/1147857262009914112922803/

lovebet爱博体育 11lovebet爱博体育 12

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int cat[110][110];//每一位存放大数的4位
 6 //Catalan数的组合公式为 Cn=C(2n,n) / (n+1);
 7 //递推公式为 h(n) = h(n - 1)*(4 * n - 2) / (n + 1);
 8 int length[110];//记录每一位卡特兰数的位数
 9 const int MOD = 10000;
10 void Init()
11 {//求出1~100位卡特兰数
12     memset(cat, 0, sizeof(cat));
13     cat[1][0] = 1;
14     int len = 1;
15     length[1] = 1;
16     for (int i = 2; i <= 100; i++)
17     {
18         //乘法
19         int r = 0;
20         for (int j = 0; j < len; j++)
21         {
22             int temp = cat[i - 1][j] * (4 * i - 2);
23             cat[i][j] = (temp+r)%MOD;
24             r = (temp + r) / MOD;
25         }
26         //进位
27         while (r)
28         {
29             cat[i][len++] = r %MOD;
30             r /= MOD;
31         }
32         //除法
33         r = 0;
34         for (int j = len - 1; j >= 0; --j)
35         {
36             int temp = r * MOD + cat[i][j];
37             cat[i][j] = temp / (i + 1);
38             r = temp % (i + 1);
39         }
40         //除法结束后高位0处理
41         while (cat[i][len - 1] == 0)
42         {
43             len--;
44         }
45         length[i] = len;
46     }
47 }
48 int main()
49 {
50     Init();
51     int n;
52     while (~scanf("%d", &n))
53     {
54         int len = length[n];
55         printf("%d", cat[n][len - 1]);
56         for (int j = len - 2; j >= 0; j--) printf("%.4d", cat[n][j]);
57         printf("\n");
58     }
59     return 0;
60 }

View Code

7、HDU 1297 Children’s
Queue(模拟大数加法<高精度递推>)

  题意:F代表女孩,M代表男孩,女孩无克独出现但好无出新,即不可知起MFM这种场馆,给得一个数n,问出稍许种站队模式。

  思路:

一个长度n的行可以看作一个n –
1的行再增的1独娃娃,那么些小孩就或是:
a.男孩,任何n –
1的法定队列追加1独男孩必然是官的,境况屡屡也f[n – 1];
b.女孩,在前n –
1的坐女孩为终极的排后搭1位女孩也是官方的,我们可以转化为n –
2的队中长2位女孩;
一如既往种植状态是在n –
2的合法队列中追加2位女孩,境况屡屡也f[n – 2];
唯独我们注意到本题的难关,可能前n –
2位为女孩啊终极的不合法队列(即单独为1各样女孩最终),也可长2位女孩成合法队列,而这种n

  • 2未合法队列必然是由于n – 4合法队列 + 1男孩 + 1女孩的结构,即情状屡屡也f[n
  • 4]。
    f[n] = f[n – 1] + f[n – 2] + f[n –
    4]。

lovebet爱博体育 13lovebet爱博体育 14

 1 //一个长度n的队列可以看成一个n - 1的队列再追加的1个小孩,这个小孩只可能是:
 2 //a.男孩,任何n - 1的合法队列追加1个男孩必然是合法的,情况数为f[n - 1];
 3 //b.女孩,在前n - 1的以女孩为末尾的队列后追加1位女孩也是合法的,我们可以转化为n - 2的队列中追加2位女孩;
 4 //一种情况是在n - 2的合法队列中追加2位女孩,情况数为f[n - 2];
 5 //但我们注意到本题的难点,可能前n - 2位以女孩为末尾的不合法队列(即单纯以1位女孩结尾),也可以追加2位女孩成为合法队列,而这种n - 2不合法队列必然是由n - 4合法队列 + 1男孩 + 1女孩的结构,即情况数为f[n - 4]。
 6 //f[n] = f[n - 1] + f[n - 2] + f[n - 4]
 7 #include<iostream>
 8 #include<cstring>
 9 using namespace std;
10 int f[1010][1010];
11 int length[1010];
12 void Init()
13 {
14     memset(f, 0, sizeof(f));
15     f[1][0] = 1;
16     f[2][0] = 2;
17     f[3][0] = 4;
18     f[4][0] = 7;
19     int len = 1;
20     length[1] = length[2] = length[3] = length[4] = 1;
21     for (int i = 5; i <= 1000; i++)
22     {
23         for (int j = 0; j < len; j++)
24         {
25             f[i][j] += f[i - 1][j] + f[i - 2][j] + f[i - 4][j];
26             f[i][j + 1] += f[i][j] / 10000;
27             f[i][j] %= 10000;
28         }
29         while (f[i][len]) len++;
30         length[i] = len;
31     }
32 }
33 int main()
34 {
35     Init();
36     int n;
37     while (~scanf("%d", &n))
38     {
39         int len = length[n];
40         printf("%d", f[n][len - 1]);
41         for (int i = len - 2; i >= 0; i--) printf("%04d", f[n][i]);
42         printf("\n");
43     }
44     return 0;
45 }

View Code

8、hdu 1466 统计直线交点数

  题意:平面上暴发n条直线,且不论三丝共点,问这个直线能发出略种不同交点数。比如,假若n=2,则恐的交点数量为0(平行)或者1(不平行)。

  思路:

分析在第N长条直线的图景(这里因为N=4为条例): 
(分类方法:和第N漫漫直线平行的于a组,此外在b组) 
1、 第四久与另外直线全体平行 :

0+4*0+0=0; 

2、 第四长条及其间有数长条平行:

交点数为0+(n-1)*1+0=3; 

3、 第四漫漫与中同样修平行:

就简单久平行直线与此外两触及直线的交点数为(n-2)*2=4,

若此外两长条直线既可能平行也说不定相交,

故而恐怕至点数也: 0+(n-2)* 2+0=4  
 或者  0+(n-2)*2+1=5     

4、
第四条直线不与外一样久直线平行,交点数也:0+(n-3)*3+0=3  或0+
(n-3)*3+2=5  或0+ (n-3)*3+3=6 

纵使n=4时,有0单,3单,4单,5只,6只不同交点数。

因此于上述n=4的解析过程被,我们发现: 

m条直线的交点方案往往 =(m –
r)条平行线与r条直线交叉的交点数 + r长长的直线本身的交点方案 = (m – r )*
r + r 条之间我的交点方案往往(0 < = r < m )

以 n 条直线排成一个队列,直线 2 暨直线 1
最多特发一个交点,直线 3 和直线 1 和直线 2
最多来少单交点……直线n和别的 n – 1 漫漫直线最多出 n – 1 独交点,由此得出
n 条直线互免平行且无三线共同点的无限多到点数:max = 1 + 2 + . . . + (n – 1)
= n * (n – 1) / 2。

里面每个自由直线与每个平行直线都发生一个交点,j自由直线与i平行直线的交点数为
j *
i,所以n条直线的交点数等于随便直线与平直线的交点加上自由直线内部形成的交点。

————————以上摘自:http://blog.csdn.net/wang907553141/article/details/52165629

lovebet爱博体育 15lovebet爱博体育 16

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 210;
 4 bool dp[25][maxn];//dp[i][j]表示i条直线相交时是否有j个交点
 5 void Init()
 6 {
 7     for (int i = 0; i <= 20; i++) dp[i][0] = true;//所有的直线都平行
 8     for (int i = 2; i <= 20; i++)
 9     {//i条直线
10         for (int j = 1; j < i; j++)
11         {//枚举和第i条边相交的边的数目
12             for (int k = 0; k < maxn; k++)
13             {//枚举j条边的交点情况
14                 if (dp[j][k]) dp[i][(i - j)*j + k] = true;
15             }
16 
17         }
18     }
19 }
20 
21 int main()
22 {
23     Init();
24     int n;
25     while (~scanf("%d", &n))
26     {
27         for (int i = 0; i < maxn; i++)
28         {
29             if (dp[n][i])
30             {
31                 if (i > 0) printf(" ");
32                 printf("%d", i);
33             }
34         }
35         printf("\n");
36     }
37     return 0;
38 }

View Code

 9、SPOJ 2832 Find The Determinant
III(n阶行列式求值)

  题意:求矩阵行列式A的值%P。

  思路:辗转相除法求n阶行列式的价对mod取模。

 

lovebet爱博体育 17lovebet爱博体育 18

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int inf = 0x3f3f3f3f;
 7 const double eps = 1e-15;
 8 typedef long long LL;
 9 const int N = 250;
10 
11 LL mat[N][N];
12 
13 LL Det(int n, int mod)
14 {//辗转相除法求n阶行列式的值对mod取模
15     //输入:mat[][]矩阵
16     for (int i = 0; i < n; ++i)
17     {
18         for (int j = 0; j < n; ++j)
19         {
20             mat[i][j] %= mod;
21         }
22     }
23     LL res = 1;
24     for (int i = 0; i < n; ++i)
25     {
26         if (!mat[i][i])
27         {
28             bool flag = false;
29             for (int j = i + 1; j < n; ++j)
30             {
31                 if (mat[j][i])
32                 {
33                     flag = true;
34                     for (int k = i; k < n; ++k)
35                     {
36                         swap(mat[i][k], mat[j][k]);
37                     }
38                     res = -res;
39                     break;
40                 }
41             }
42             if (!flag)
43             {
44                 return 0;
45             }
46         }
47         for (int j = i + 1; j < n; ++j)
48         {
49             while (mat[j][i])
50             {
51                 LL t = mat[i][i] / mat[j][i];
52                 for (int k = i; k < n; ++k)
53                 {
54                     mat[i][k] = (mat[i][k] - t * mat[j][k]) % mod;
55                     swap(mat[i][k], mat[j][k]);
56                 }
57                 res = -res;
58             }
59         }
60         res = (res * mat[i][i]) % mod;
61     }
62     return (res + mod) % mod;
63 }
64 
65 int main()
66 {
67     int n;
68     LL p;
69     while (~scanf("%d%lld", &n, &p))
70     {
71         for (int i = 0; i < n; ++i)
72         {
73             for (int j = 0; j < n; ++j)
74             {
75                 scanf("%lld", &mat[i][j]);
76             }
77         }
78         LL ans = Det(n, p);
79         printf("%lld\n", ans);
80     }
81     return 0;
82 }

View Code

 

相关文章