1498C - Planar Reflections （暴力+前缀和+模拟）

小灰灰 2021-07-16 18:38 362阅读 0赞

[题目][Link 1]

思路：模拟一下过程，有n个平面，那么在一次飞跃中位于第1个平面的粒子向右飞会在后面每个平面都产生一个粒子，那第一个平面有m个粒子后面每个平面2–n都产生m个粒子，同理第二个平面的每个粒子也会对其后面的所有平面产生一个粒子。然后最共会裂变n-1次进行这么多次飞跃,每一次飞跃记录结果作为下一次飞跃的各平面所拥有的粒子数,再每次飞跃变换一下方向即可。再来看一下数据大小n<=1000,k<=1000。  
如果直接暴力模拟 O(n^3)，但对于给第i个平面后面所有平面粒子+1的操作可以用前缀和处理，复杂度变为 O(n^2)，细节见代码。

Code:

#include<iostream>
    #include<memory.h>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    const int Mod = 1e9 + 7;
    int lst[1005], ls[1005];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		memset(lst, 0, sizeof(lst));
    		int n, k;cin >> n >> k;
    		ll ans = 1, sum = 0;//一开始ans有一个粒子
    		for (int i = 1;i <= k - 1;i++)
    		{ 
    			memset(ls, 0, sizeof(ls));
    			sum=0;
    			if (i % 2 == 1)
    			{ 
    				for (int j = 1;j <= n;j++)	ls[j + 1] += lst[j];
    				if (i == 1)ls[1] = 1;//一开始有一个粒子的初始化
    				for (int j = 1;j <= n;j++)
    				{ 
    					sum = (sum + ls[j]) % Mod;
    					ans = (ans + sum) % Mod;
    					lst[j] = sum;
    				}
    			}
    			else
    			{ 
    				for (int j = n;j >= 1;j--)	ls[j - 1] += lst[j];
    				for (int j = n;j >= 1;j--)
    				{ 
    					sum = (sum + ls[j]) % Mod;
    					ans = (ans + sum) % Mod;
    					lst[j] = sum;
    				}
    			}
    		}
    		cout << ans << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1498/problem/C