Nowcoder 北师校赛 B 外挂使用拒绝 ( k次前缀和、矩阵快速幂打表找规律、组合数 )
2024-09-01 17:08:12
题意 : 中文题、点链接
分析 :
有道题是问你不断求前缀和后的结果 Click here
这道题问的是逆过程
分析方法雷同、可参考 Click here
--------------------------------------------------------------------------------
正着做的矩阵是一个下三角
1 0 0 0
1 1 0 0
1 1 1 0
1 1 1 1
结合杨辉三角可得
C(k, 0)
C(k+1, 1) C(k, 0)
C(k+2, 2) C(k+1, 1) C(k, 0)
C(k+3, 3) C(k+2, 2) C(k+1, 1) C(k, 0)
......
--------------------------------------------------------------------------------
逆过程是这样一个矩阵
1 0 0 0
-1 1 0 0
0 -1 1 0
0 0 -1 1
结合杨辉三角可得
A[i][j] = (-1)^(i-j) * C(k, i-j)
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scl(i) scanf("%lld", &i) #define scll(i, j) scanf("%lld %lld", &i, &j) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l) #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l) #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l) #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define VI vector<int> #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define VL vector<long long> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> #define _TIME 0 #define _INPUT 0 #define _OUTPUT 0 clock_t START, END; void __stTIME(); void __enTIME(); void __IOPUT(); using namespace std; ; ; LL arr[maxn]; LL A[maxn][maxn]; LL Comb[maxn]; LL inv[maxn]; inline void inv_init() { inv[] = inv[] = ; ; i<maxn; i++) inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod; } int main(void){__stTIME();__IOPUT(); inv_init(); int n, k; int nCase; sci(nCase); while(nCase--){ scii(n, k); LL tmp = ; Comb[] = 1LL; ; i<=min(k, n); i++){ Comb[i] = Comb[i-]%mod; Comb[i] = ( Comb[i] * (k-i+) ) % mod; Comb[i] = ( Comb[i] * inv[i] ) %mod; } ; i<=n; i++) scl(arr[i]); ; i<=n; i++){ ; j<=i; j++){ if(i-j > k){ A[i][j] = 0LL; continue; } ) A[i][j] = -1LL; else A[i][j] = 1LL; A[i][j] = ( ( (A[i][j] * Comb[i-j])%mod) + mod) % mod; } } ; i<=n; i++){ LL ans = ; ; j<=n; j++) ans = ((ans + (A[i][j] * arr[j])%mod + mod)%mod)%mod; printf("%lld", ans%mod); if(i != n) putchar(' '); }puts(""); } __enTIME();;} void __stTIME() { #if _TIME START = clock(); #endif } void __enTIME() { #if _TIME END = clock(); cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl; #endif } void __IOPUT() { #if _INPUT freopen("in.txt", "r", stdin); #endif #if _OUTPUT freopen("out.txt", "w", stdout); #endif }
最新文章
- webstorm 10 更改默认端口
- 2-sat按照最小字典序输出可行解(hdu1814)
- Java基于Socket文件传输示例(转)
- PHP过滤常用标签的正则表达式
- golang做的邮件服务器
- Andrew 机器学习课程笔记
- print,printf,println
- 如何彻底删除mysql
- Eclipse简介和使用技巧快捷方式
- [Java JNI] [Windows] [Visual Studio] [DLL] [UnsatisfiedLinkError]
- gcc 头文件依赖关系 分析工具
- [Bug]Unable to start process dotnet.exe
- logback -- 配置详解 -- 三 -- <;encoder>;
- SecureCRT和乱码
- RSS是什么,RSS怎么玩,RSS原理是什么 (zhuan)
- 版本控制工具(上)——Git的基本使用
- Java基础 - 面向对象 - 构造方法
- BFC(Block Formatting Context)基础分析
- PAT L2-019 悄悄关注
- int 与 string::length()