博客园食用更佳 关注洛谷谢谢喵~
先看例题：
先看数据范围，n ≤ 1 0 500 n \le 10^{500} n ≤ 1 0 500
d p i dp_i d p i i i i 4 4 4 3 3 3 m o d 2 , 3 , 4 \bmod 2,3,4 mod 2 , 3 , 4 0 ∼ 3 0 \sim 3 0 ∼ 3 11 × 11 11 \times 11 11 × 11 log 1 0 500 \log 10^{500} log 1 0 500 1660 1660 1660 d p n dp_n d p n
但是这样还是太慢了，有没有更快又更简单不用构造转移矩阵的方法呢，有的兄弟有的，我们生成函数就可以登场了。
我们发现，假如现在选 a a a b b b a + 1 a+1 a + 1 b b b a a a b b b a a a b b b b × x a b \times x^a b × x a ( x + 1 ) (x+1) ( x + 1 ) b × x a × ( x + x 0 ) b \times x^a \times(x+x^0) b × x a × ( x + x 0 ) b × x a + b × x a + 1 b \times x^a + b \times x^{a+1} b × x a + b × x a + 1 x x x
那么显然有初值 x 0 x^0 x 0 0 0 0 1 1 1
汉堡：∑ i = 0 ∞ x 2 i \sum_{i=0}^{\infty} x^{2i} ∑ i = 0 ∞ x 2 i
可乐：x 0 + x 1 x^0+x^1 x 0 + x 1
鸡腿：x 0 + x 1 + x 2 x^0+x^1+x^2 x 0 + x 1 + x 2
蜜桃多：∑ i = 0 ∞ x 2 i + 1 \sum_{i=0}^{\infty} x^{2i+1} ∑ i = 0 ∞ x 2 i + 1
鸡块：∑ i = 0 ∞ x 4 i \sum_{i=0}^{\infty} x^{4i} ∑ i = 0 ∞ x 4 i
包子：x 0 + x 1 + x 2 + x 3 x^0+x^1+x^2+x^3 x 0 + x 1 + x 2 + x 3
土豆片炒肉：x 0 + x 1 x^0+x^1 x 0 + x 1
面包：∑ i = 0 ∞ x 3 i \sum_{i=0}^{\infty} x^{3i} ∑ i = 0 ∞ x 3 i
发现乘上一个 x a x^a x a a a a x n x^n x n
但是发现有一些式子是有无穷项的，无法乘在一起，所以我们考虑求出其封闭形式 。
引理 1 1 1 ∑ i = 0 ∞ x i = 1 1 − x ( ∣ x ∣ < 1 ) \sum_{i=0}^{\infty} x^i=\dfrac{1}{1-x}(|x|<1) ∑ i = 0 ∞ x i = 1 − x 1 ( ∣ x ∣ < 1 )
该引理被称为几何级数公式 。证明考虑等比数列求和公式，原式可变为 x ∞ − 1 x − 1 \dfrac{x^\infty-1}{x-1} x − 1 x ∞ − 1 ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1 x ∞ x^\infty x ∞ 0 0 0 1 1 − x \dfrac{1}{1-x} 1 − x 1
这里可能有读者疑惑，可以保证 ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1 x x x 0 0 0 ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1
同理 ∑ i = 0 ∞ x 2 i = 1 1 − x 2 , ∑ i = 0 ∞ x 4 i = 1 1 − x 4 \sum_{i=0}^{\infty} x^{2i}=\dfrac{1}{1-x^2},\sum_{i=0}^{\infty} x^{4i}=\dfrac{1}{1-x^4} ∑ i = 0 ∞ x 2 i = 1 − x 2 1 , ∑ i = 0 ∞ x 4 i = 1 − x 4 1
那么重新写出：
汉堡：1 1 − x 2 \frac{1}{1-x^2} 1 − x 2 1
蜜桃多：x 1 − x 2 \frac{x}{1-x^2} 1 − x 2 x
鸡块：1 1 − x 4 \frac{1}{1-x^4} 1 − x 4 1
面包：1 1 − x 3 \frac{1}{1-x^3} 1 − x 3 1
那么最后乘法就比较简单了，这里直接给出化简之后的结果 x × ( x − 1 ) − 4 x \times (x-1)^{-4} x × ( x − 1 ) − 4 x n x^n x n
设 α \alpha α i i i
( α i ) = { 0 , ( i l t ; 0 ) 1 , ( i = 0 ) α ( α − 1 ) ⋯ ( α − i + 1 ) i ! , ( i g t ; 0 ) {\alpha \choose i}=\begin{cases}0,&(i<0)\\1,&(i=0)\\\frac{\alpha(\alpha-1)\cdots(\alpha-i+1)}{i!},&(i>0)\end{cases}
( i α ) = ⎩ ⎨ ⎧ 0 , 1 , i ! α ( α − 1 ) ⋯ ( α − i + 1 ) , ( i ( i = 0 ) ( i lt ; 0 ) g t ; 0 )
引理 2 2 2 ( x + y ) α = ∑ i = 0 ∞ ( α i ) x i y α − i (x+y)^{\alpha}=\sum_{i=0}^{\infty} {\alpha \choose i} x^i y^{\alpha-i} ( x + y ) α = ∑ i = 0 ∞ ( i α ) x i y α − i
这个引理被称为广义牛顿二项式定理 ，读者自证不难。
则原式变为：x × ∑ i = 0 ∞ ( − 4 i ) x i ( − 1 ) − 4 − i x \times \sum_{i=0}^{\infty} {-4\choose i}x^i(-1)^{-4-i} x × ∑ i = 0 ∞ ( i − 4 ) x i ( − 1 ) − 4 − i ( α i ) \alpha\choose i ( i α ) ( − 1 ) i (-1)^i ( − 1 ) i ( − 1 ) i × ( − α + i − 1 ) ( − α + i ) ⋯ − α i ! = ( − 1 ) i × ( i − α − 1 i ) (-1)^i \times \dfrac{(-\alpha+i-1)(-\alpha+i)\cdots-\alpha}{i!}=(-1)^i \times {{i-\alpha-1}\choose i} ( − 1 ) i × i ! ( − α + i − 1 ) ( − α + i ) ⋯ − α = ( − 1 ) i × ( i i − α − 1 ) α = 4 \alpha=4 α = 4 ( − 4 i ) = ( i + 3 i ) {-4\choose i}={i+3\choose i} ( i − 4 ) = ( i i + 3 )
x × ∑ i = 0 ∞ ( − 4 i ) x i ( − 1 ) − 4 − i = x × ∑ i = 0 ∞ ( i + 3 i ) x i ( − 1 ) − 4 − i ( − 1 ) i = ∑ i = 0 ∞ ( i + 3 i ) x i + 1 = ∑ i = 1 ∞ ( i + 2 3 ) x i = ∑ i = 1 ∞ i ( i + 1 ) ( i + 2 ) 6 × x i \begin{aligned}&x \times \sum_{i=0}^{\infty} {-4\choose i}x^i(-1)^{-4-i}\\&= x \times \sum_{i=0}^{\infty} {i+3\choose i} x^i(-1)^{-4-i}(-1)^i\\&=\sum_{i=0}^{\infty} {i+3\choose i} x^{i+1}\\&=\sum_{i=1}^{\infty} {i+2\choose 3}x^i\\&= \sum_{i=1}^{\infty} \dfrac{i(i+1)(i+2)}{6} \times x^i \end{aligned}
x × i = 0 ∑ ∞ ( i − 4 ) x i ( − 1 ) − 4 − i = x × i = 0 ∑ ∞ ( i i + 3 ) x i ( − 1 ) − 4 − i ( − 1 ) i = i = 0 ∑ ∞ ( i i + 3 ) x i + 1 = i = 1 ∑ ∞ ( 3 i + 2 ) x i = i = 1 ∑ ∞ 6 i ( i + 1 ) ( i + 2 ) × x i
化简完成，由此我们知道了 x n x^n x n n ( n + 1 ) ( n + 2 ) n(n+1)(n+2) n ( n + 1 ) ( n + 2 )
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=10007 ;
int n;
inline int read () int t=0 ,f=1 ;
register char c=getchar ();
while (c<48 ||c>57 ) f=(c=='-' )?(-1 ):(f),c=getchar ();
while (c>=48 &&c<=57 )t=(t<<1 )+(t<<3 )+(c^48 ),c=getchar ();
return f*t;
}
void solution () int ksm (int x,int y) int sum=1 ;
while (y){
if (y&1 ) sum=sum*x%mod;
x=x*x%mod;y>>=1 ;
}
return sum;
}
signed main () for (int i=0 ;i<s.size ();i++){
int x=s[i]-'0' ;
n=n*10 +x;n%=mod;
}
n=(n+1 )*(n+2 )%mod*n%mod;
n=n*ksm (6 ,mod-2 )%mod;
cout<<n<<"\n" ;
return 0 ;
}
依旧采用上一题的思路，考虑将 x k x^k x k k k k ∑ j = 0 m i x j \sum_{j=0}^{m_i} x^j ∑ j = 0 m i x j 0 , 1 , ⋯ , m i 0,1,\cdots,m_i 0 , 1 , ⋯ , m i
发现 m i m_i m i f i = ∑ j = 0 m i x j f_i=\sum_{j=0}^{m_i} x^j f i = ∑ j = 0 m i x j f i × x = ∑ j = 1 m i + 1 x j f_i \times x =\sum_{j=1}^{m_i+1} x^j f i × x = ∑ j = 1 m i + 1 x j f i × ( x − 1 ) = x m i + 1 − 1 f_i \times (x-1)=x^{m_i+1}-1 f i × ( x − 1 ) = x m i + 1 − 1 f i = x m i + 1 − 1 x − 1 f_i=\dfrac{x^{m_i+1}-1}{x-1} f i = x − 1 x m i + 1 − 1
则所有方程的积即为 ( 1 − x ) − n × ∏ i = 1 n ( 1 − x m i + 1 ) (1-x)^{-n} \times \prod_{i=1}^n (1-x^{m_i+1}) ( 1 − x ) − n × ∏ i = 1 n ( 1 − x m i + 1 ) n n n 10 10 10 2 10 = 1024 2^{10}=1024 2 10 = 1024 ∑ i = 0 ∞ ( i + n − 1 n − 1 ) x i \sum_{i=0}^{\infty}{i+n-1\choose n-1} x^i ∑ i = 0 ∞ ( n − 1 i + n − 1 ) x i x i x^i x i ( i + n − 1 n − 1 ) {i+n-1\choose n-1} ( n − 1 i + n − 1 )
设后面的多项式为 g ( x ) = a 1 x b 1 + a 2 x b 2 + ⋯ + a p x b p g(x)=a_1x^{b_1} + a_2x^{b_2}+\cdots+a_px^{b_p} g ( x ) = a 1 x b 1 + a 2 x b 2 + ⋯ + a p x b p j j j 1 ∼ a 1\sim a 1 ∼ a a j × ∑ i = 0 a − b j ( i + n − 1 i ) = a j × ( n + a − b j a − b j ) = a j × ( n + a − b j n ) a_j \times \sum_{i=0}^{a-b_j} {i+n-1\choose i}=a_j \times {n+a-b_j \choose a-b_j}=a_j \times {n+a-b_j \choose n} a j × ∑ i = 0 a − b j ( i i + n − 1 ) = a j × ( a − b j n + a − b j ) = a j × ( n n + a − b j ) ( n m ) = ( n − 1 m − 1 ) + ( n − 1 m ) {n \choose m}={n-1 \choose m-1}+{n-1 \choose m} ( m n ) = ( m − 1 n − 1 ) + ( m n − 1 ) ( n − 1 0 ) {n-1\choose 0} ( 0 n − 1 ) ( n 0 ) {n\choose 0} ( 0 n )
那么问题来到了求一个组合数模 2004 2004 2004 ( n m ) = n ! ( n − m ) ! m ! {n \choose m}=\dfrac{\frac{n!}{(n-m)!}}{m!} ( m n ) = m ! ( n − m )! n ! x x x x = 2004 × p × m ! + q × m ! ( q < 2004 ) x=2004 \times p \times m! + q \times m!(q<2004) x = 2004 × p × m ! + q × m ! ( q < 2004 ) m ! ∣ x m!|x m ! ∣ x x x x m ! m! m ! x x x 2004 × m ! 2004 \times m! 2004 × m ! m ! m! m !
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (1e18)
#define pr pair<int,int>
const int N=12 ;
const int mod=2004 ;
int n,l,r;
int m[N];
vector<pr > g;
inline int read () int t=0 ,f=1 ;
register char c=getchar ();
while (c<48 ||c>57 ) f=(c=='-' )?(-1 ):(f),c=getchar ();
while (c>=48 &&c<=57 )t=(t<<1 )+(t<<3 )+(c^48 ),c=getchar ();
return f*t;
}
void solution () void dfs (int dang,int sum,int sum1) if (dang>n){
g.push_back ({(sum1&1 ?-1 :1 ),sum});
return ;
}
dfs (dang+1 ,sum,sum1);
dfs (dang+1 ,sum+m[dang]+1 ,sum1+1 );
}
int calc (int x,int y) int val=1 ,val1=1 ;
for (int i=1 ;i<=y;i++) val1*=i;val1*=2004 ;
for (int i=x-y+1 ;i<=x;i++) val=val*i%val1;
val/=(val1/2004 );
return val;
}
int solve (int xx) int res=0 ;
for (pr i:g){
int x=i.first,y=i.second;
if (xx<y) continue ;
res=(res+x*calc (n+xx-y,n)%mod)%mod;
}
return res;
}
signed main () read (),l=read (),r=read ();
for (int i=1 ;i<=n;i++) m[i]=read ();
dfs (1 ,0 ,0 );int ans=solve (r)-solve (l-1 );
ans=(ans%mod+mod)%mod;
cout<<ans<<"\n" ;
return 0 ;
}
有帮助，赞一个