题目链接
题意 : 中文题, 点链接
分析 :
有道题是问你不断求前缀和后的结果 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;
- const int maxn = 1e3 + 5;
- const LL mod = 1e9 + 7;
- LL arr[maxn];
- LL A[maxn][maxn];
- LL Comb[maxn];
- LL inv[maxn];
- inline void inv_init()
- {
- inv[0] = inv[1] = 1;
- for(int i=2; 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 = 0;
- Comb[0] = 1LL;
- for(int i=1; i<=min(k, n); i++){
- Comb[i] = Comb[i-1]%mod;
- Comb[i] = ( Comb[i] * (k-i+1) ) % mod;
- Comb[i] = ( Comb[i] * inv[i] ) %mod;
- }
- for(int i=1; i<=n; i++) scl(arr[i]);
- for(int i=1; i<=n; i++){
- for(int j=1; j<=i; j++){
- if(i-j> k){
- A[i][j] = 0LL;
- continue;
- }
- if((i-j) & 1) A[i][j] = -1LL;
- else A[i][j] = 1LL;
- A[i][j] = ( ( (A[i][j] * Comb[i-j])%mod) + mod) % mod;
- }
- }
- for(int i=1; i<=n; i++){
- LL ans = 0;
- for(int j=1; j<=n; j++)
- ans = ((ans + (A[i][j] * arr[j])%mod + mod)%mod)%mod;
- printf("%lld", ans%mod);
- if(i != n) putchar(' ');
- }puts("");
- }
- __enTIME();return 0;}
- 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
- }
来源: http://www.bubuko.com/infodetail-2748424.html