HDU4602-Partition(矩阵乘法)

题目链接：HDU4602

【题意】给出n，k(<=10^9)，在用1~n的数字的所有排列相加==n中，数字k出现的次数；

【分析】首先很容易发现任何n出现次数都是由1，2，5，12…这样一个规律倒着出现，例如n = 4时，1出现12次，2出现5次，3出现2次，4出现1次…这样类推，用cnt[i]记录这个1,2,5,12…序列，则n,k的答案就是cnt[n-k+1];当k>n是要特判为0

然后就是怎么快速求出这个序列了，通过暴力打表发现一个递推式：cnt[i]=sum[i-1]+p[i-1];其中cnt[i]表示第i个数字出现的次数，sum[i]是cnt[1]~cnt[i]的和，p[i-1]是2^(i-1)；但是n有10^9，显然不能用递推式求和存；然后想到了用矩阵乘法求；为了简单把原式转换一下变成sum[i]=2*sum[i-1]+p[i-1];这样cnt[i]=sum[i]-sum[i-1]；sum[1] = 1;然后只要构造出一个矩阵

X=｛2，0

1，2｝；

在构造一个矩阵A={sum[i-1],p[i-1]}

则A*X = {2*sum[i-1]+p[i-1], 2*p[i-1]} == {sum[i],p[i]}；

这样A* X^n-1次就是{sum[n],p[n]};sum[n]算出来，sum[n-1]再算一下，答案就出来了；

【AC CODE】265ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MOD = 1000000000+7;
/* sum[i] = 2*sum[i-1]+p[i-1]&&p[i]=2*p[i-1] sum[1] = 1 p[1] = 1*/
struct MATRIX{
    LL num[2][2];
    MATRIX(LL a1, LL a2, LL b1, LL b2)
    {
        num[0][0] = a1, num[1][0] = a2;
        num[0][1] = b1, num[1][1] = b2;
    }
};
MATRIX x = MATRIX(2,1,0,2);

MATRIX mul(const MATRIX &a, const MATRIX &b)
{
    MATRIX ans = MATRIX(0,0,0,0);
    rep(i,0,2)
    {
        rep(j,0,2)
        {
            rep(k,0,2)
                ans.num[i][j] = (ans.num[i][j]+a.num[i][k]*b.num[k][j]%MOD)%MOD;
        }
    }
    return ans;
}
MATRIX pow_mod(MATRIX x, int n)
{
    MATRIX ans = MATRIX(1,0,0,1);
    while(n)
    {
        if(n&1) ans = mul(ans,x);
        x = mul(x,x);
        n >>= 1;
    }
    return ans;
}
int main()
{
#ifdef SHY
    freopen("e:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d%*c", &t);
    while(t--)
    {
        int n,k;
        scanf("%d %d%*c", &n, &k);
        if(k >= n)
        {
            if(k == n) puts("1");
            else puts("0");
            continue;
        }
        n = n-k+1;
        MATRIX p = pow_mod(x,n-1);
        LL ans = (p.num[0][0]+p.num[1][0])%MOD;
        p = pow_mod(x,n-2);
        ans = (ans-(p.num[0][0]+p.num[1][0])%MOD+MOD)%MOD;
        printf("%I64d\n", ans);
    }
    return 0;
}

 

【暴力代码】

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000;
int cnt[MAXN], n, num[MAXN];

void dfs(int sum, int p)
{
	if(sum == n)
	{
		repe(i,1,p) cnt[num[i]]++;
		return;
	}
	repe(i,1,n-sum)
	{
		num[p+1] = i;
		dfs(sum+i,p+1);
	}
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int t;
	n = 20;
	clc(cnt,0);
	dfs(0,0);
	int sum = 0;
	printf("num cnt\t\tpow\tsum\tsum-pow\t\tcnt-pow\n");
	repe(i,1,n)
	{
		sum += cnt[n-i+1];
		printf("%2.d: %-10.d %-10.0lf %-10d %-10.0lf %-10.0lf %-10.0lf\n", i,cnt[n-i+1],  pow(2,i-1),sum,sum-pow(2,i-1),cnt[n-i+1]-pow(2,i-1),sum-cnt[n-i+1]+pow(2,i-2));
		//printf("%d-%d: %d\n", i,i-1,cnt[n-i+1]-cnt[n-i+2]);
	}
	return 0;
}