772002画马尾

题目连接：

http://acm.uestc.edu.cn/#/problem/show/1280

Description

众所周知772002很喜欢马尾，所以他决定画几幅马尾送给他的女朋友。

772002会画m种马尾，772002还有n张纸，n张纸分别编号1到n，每张纸上只能画一种马尾。

然而772002的女朋友只喜欢其中t种马尾。并且772002的女朋友只喜欢偶数（因为这象征着成对成双）。

772002想知道有多少种画法，使得n张纸画满并且自己女朋友喜欢的那t种马尾每种个数都恰好为偶数。

然而772002陪女朋友看电影去了，所以他把这个问题交给了你，你能解决吗？

Input

一行，三个整数m,n,t。

1-50组数据 m≤2，t≤m，n≤100

51-100组数据 m≤5，t≤m，n≤10000

101-300组数据 m≤10，t≤m，n≤1000000000

Output

一个整数,表示方案数，因为这个数比较大，所以输出对10007求余的结果。

Sample Input

2 93 1

Sample Output

8605

Hint

题意

题解：

比较显然的是dp[i][j] = dp[i-1][j-1]*(t-j+1) + dp[i-1][j]*(m-t) + dp[i-1][j+1]*(j+1)

然后这个东西是可以化成矩阵的

然后矩阵快速幂暴力一波就好了。

代码

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

int n,m,t,i,x[11][11];

int mo=10007;

void multiply(int a[11][11],int b[11][11])

{

    int i,j,k,c[11][11];

    for (i=0;i<=t;i++)

        for (j=0;j<=t;j++)

        {

            c[i][j]=0;

            for (k=0;k<=t;k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mo;

        }

    for (i=0;i<=t;i++)

        for (j=0;j<=t;j++)

            a[i][j]=c[i][j];

}

void binary(int x[11][11],int a)

{

    int i,j,y[11][11];

    if (a==1) return;

    for (i=0;i<=t;i++)

        for (j=0;j<=t;j++)

            y[i][j]=x[i][j];

    multiply(x,x);

    binary(x,a/2);

    if (a%2==1) multiply(x,y);

}

int main()

{

    scanf("%d%d%d",&m,&n,&t);

    for (i=0;i<=t;i++)

	{

        if (i!=0) x[i-1][i]=t-i+1;

        x[i][i]=m-t;

        if (i!=t) x[i+1][i]=i+1;

	}

	binary(x,n);

	printf("%d\n",x[0][0]);

}

巴特西

CDOJ 1280 772002画马尾每周一题 div1 矩阵快速幂

772002画马尾

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

巴特西

CDOJ 1280 772002画马尾 每周一题 div1 矩阵快速幂

772002画马尾

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

CDOJ 1280 772002画马尾每周一题 div1 矩阵快速幂