bzoj 5015 [Snoi2017]礼物

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=5015

题解

首先把k=1,k=2,k=3的手推一遍

然后发现一些规律就是数列可以表示成$a_i=2a_{i-1}+f(i)$的形式

然后f(i)算一算之后我们得到

然后我们试图求这个东西的通项公式

我们要把它变成$a_i+f(i)=2(a_{i-1}+f(i-1))$的形式就好了

那么我们设

一共k个变量对于每一个$n^i$我们根据他的系数可以列一个方程一共k个方程

所以高斯消元把它解出来就结束了

Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll read(){
 6     ll x=0,f=1;char c=getchar();
 7     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
 8     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
 9     return x*f;
10 }
11 
12 const ll mod=1000000007ll;
13 ll n;
14 int k;
15 ll mat[20][20];
16 
17 ll calc(ll a,ll b){
18     ll ret=1;
19     for(int i=1;i<=b;i++)
20         ret=ret*(a-i+1)/i;
21     return ret%mod;
22 }
23 
24 ll ksm(ll a,ll b){
25     if(b==0) return 1;
26     ll nw=1;
27     if(b==1) return a%mod;
28     if(b&1) nw=a;
29     ll ret=ksm(a,b/2);
30     return ret*(nw%mod)%mod*ret%mod;
31 }
32 
33 inline ll pd(ll x){
34     if(x&1) return -1;
35     return 1;
36 }
37 ll ans[20];
38 
39 int main(){
40     #ifdef LZT
41     //freopen("in","r",stdin);
42     #endif
43     n=read(),k=read();
44     for(int i=1;i<=k;i++){
45         mat[i][0]=calc(k,i)*pd(i+1);
46         mat[i][i]--;
47         int st=i-1;
48         for(int j=1;j<=i;j++)
49             mat[i][j]+=(2*calc(k-j,st)*pd(st--));
50     }
51     for(int i=1;i<=k;i++){
52         ll nw=0;
53         for(int j=1;j<i;j++) nw=nw+mat[i][j]*ans[j];
54         ans[i]=(mat[i][0]-nw)/mat[i][i];
55     }
56     for(int i=1;i<=k;i++)
57         ans[i]=ans[i]%mod;
58     ll res=ans[k]*ksm(2,n)%mod;
59     for(int i=1;i<=k;i++){
60         ll nw=ans[i]*ksm(n,k-i)%mod;
61         res=(res-nw+mod)%mod;
62     }
63     printf("%lld
",res);
64     
65     return 0;
66 }

View Code

Review

这样做的动机?

就是先把k=2,k=3的情况推了一下然后发现很相似 f(i)的次数与k相关而k很小只有10

然后就试图用程序表达手推的过程发现消元就可以了然后就做了出来