组合数学 (习题): 计蒜客 T1280

野性酷女 2022-02-15 08:41 240阅读 0赞

### 计蒜客T1280 ###

*  题目
 *  思路
 *  代码
 *  总结

# 题目 #

给定两个正整数  n n n,  P P P，求满足以下两个条件的长度为  n n n 的序列  a a a 的个数：

1.   1 ≤ a i ≤ P 1 \\le a\_i \\le P 1≤ai≤P
2.  不存在  1 ≤ l ≤ r ≤ n 1 \\le l \\le r \\le n 1≤l≤r≤n，满足  a l + a l + 1 + . . . + a r a\_l + a\_\{l+1\} + ... + a\_r al\+al\+1\+...\+ar 是  P P P 的倍数

由于方案数可能很大，你只需要输出方案数对  1 e 9 + 7 1e9+7 1e9\+7 取模的值

# 思路 #

任何一个子序列  a \[ l : r \] a\[l:r\] a\[l:r\] 的和都等于  a \[ : r \] − a \[ : l − 1 \] a\[:r\] - a\[:l-1\] a\[:r\]−a\[:l−1\], 因此问题等价于任何两个前缀和之差都不能是 P 的倍数. 所以任何两个前缀和  m o d   P mod \\space P mod P 两两不相等, 且任何一个元素都不能是  P P P.  
因为  1 ≤ a i ≤ P 1 \\le a\_i \\le P 1≤ai≤P, 所以:  
 a \[ : 0 \] a\[:0\] a\[:0\] 有  P − 1 P-1 P−1 种方案  
 a \[ : 1 \] a\[:1\] a\[:1\] 有  P − 2 P-2 P−2 种方案 (因为在给定  a \[ 0 \] a\[0\] a\[0\] 的情况下只要  a \[ 1 \] a\[1\] a\[1\] 不是  a \[ 0 \] a\[0\] a\[0\] 或者  P P P, 都有 a \[ : 1 \] ≡ ̸ a \[ : 0 \] ( m o d   P ) a\[:1\] \\equiv\\not a\[:0\] (mod \\space P) a\[:1\]≢a\[:0\](mod P) )

所以总方案数是  
 ∏ i = 1 n P − i \\prod\_\{i=1\}^nP-i ∏i=1nP−i

如果  n ≥ P n \\ge P n≥P, 那么必有两个前缀和同模, 那么方案数就是  0 0 0.

# 代码 #

#include <stdio.h>
    
    int main() { 
        int n, p;
        scanf("%d %d", &n, &p);
        long result = 1;
        if (n >= p) { 
            printf("0\n");
            return 0;
        }
        for (int i = 1; i <= n; i++) { 
            result *= p-i;
            result %= 1000000007;
        }
        printf("%ld\n", result);
    }

# 总结 #

一定要养成 **子序列之和** 等于前缀和之差的思想!